Znzryb's Blog

P5788 【模板】单调栈

Posted on 2025-06-18 Edited on 2026-02-17

思路讲解

求解右边第一个大于自己的数的下标。

AC代码

https://www.luogu.com.cn/record/220790487

源代码

// Problem: P5788 【模板】单调栈
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5788
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(3e6)+10,INF=static_cast<ll>(1e9)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN],Ans[MAXN];
/*

*/
inline void init(){
	
}
inline void solve(){
	cin>>N;
	init();
	FOR(i,1,N){
		cin>>A[i];
	}
	deque<ll> q;
	FOR(i,1,N){
		while(q.empty()==false && A[i]>A[q.back()]){
			Ans[q.back()]=i;
			q.pop_back();
		}
		q.push_back(i);
	}
	FOR(i,1,N){
		cout<<Ans[i]<<" ";
	}
	cout<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://www.luogu.com.cn/record/220790487
*/

心路历程（WA，TLE，MLE……）

Starter189-Sortable Subarrays (Easy/Hard)

Posted on 2025-06-14 Edited on 2026-02-17

思路讲解

就是问可以通过$ A_i=A_i \mod X$ 这个操作变的有序的子串有多少个？

那么注意到那，这个操作没有说那么不可控，其实就是可以变为 $[\ 0,A_i \mod (A_i/2+1)\ ]$ 中的一个。

https://www.codechef.com/viewsolution/1166421088

	FOR(i,1,N){
		ll idx=-1;
		FOR(j,i,N){
			ll val=A[j]%(A[j]/2+1);
// #ifdef LOCAL
    // debug(A[j]);debug(val);
// #endif
			if(val>idx){
				++ans;
				++idx;
			}else if(A[j]>idx){   // we observe sometime we should not make the num modded
				idx=A[j];      // such as test case 1
				++ans;
			}else{
				break;
			}
		}
	}

简单就套一个简单的O(n**2)就过了。困难要求线性复杂度，这个就比较难了。

那么我们试过了，双指针是不太能解决，因为左端点的移动不仅有可能造成右端点的变化，还有可能造成里面的变化，当然这个我们只要表征右端点就行了，但是会使得情况很复杂。

唉，读了很多遍题解，发现他应该是藏了一手，有些东西没说清楚。

$up_j≥j-i \Rightarrow up_j-j \ge -i$ 因此我们就是要找到第一个不符合这个式子的数字。

不难发现我们可以用单调栈做这个 P5788 【模板】单调栈。

但是光解决上面的这个问题不够呀，所以我们需要一步，就是推导这个如果我不去删这个数，可以得到什么效果？如果说 $A_i<j-i$ ，那么就不用管了，到头了。 $up_j\ge j-i+A_i \Rightarrow up_j-j\ge -i+A_i$ ，那么我们也可以用一样的方法去解决。

AC代码

https://www.codechef.com/viewsolution/1166421088

源代码

// Problem: Sortable Subarrays (Easy)
// Contest: CodeChef - START189
// URL: https://www.codechef.com/problems/SORTSUB7EZ
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e9)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
/*

*/
inline void init(){
	
}
inline void solve(){
	cin>>N;
	init();
	FOR(i,1,N){
		cin>>A[i];
	}
	ll ans=0;
	// [\ 0,A_i \mod (A_i/2+1)\ ]
	FOR(i,1,N){
		ll idx=-1;
		FOR(j,i,N){
			ll val=A[j]%(A[j]/2+1);
// #ifdef LOCAL
    // debug(A[j]);debug(val);
// #endif
			if(val>idx){
				++ans;
				++idx;
			}else if(A[j]>idx){
				idx=A[j];
				++ans;
			}else{
				break;
			}
		}
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://www.codechef.com/viewsolution/1166421088
*/

加了一个记忆化搜索就好了。

https://www.codechef.com/viewsolution/1166895091

源代码

// Problem: Sortable Subarrays (Hard)
// Contest: CodeChef - START189
// URL: https://www.codechef.com/problems/SORTSUB7?tab=statement
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e9)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN],up[MAXN],fib[MAXN],seb[MAXN];
/*

*/
inline void init(){
	FOR(i,1,N){
		fib[i]=N;
		seb[i]=N;
	}
}
inline void solve(){
	cin>>N;
	init();
	FOR(i,1,N){
		cin>>A[i];
	}
	// [\ 0,A_i \mod (A_i/2+1)\ ]
	FOR(i,1,N){
		up[i]=A[i]%(A[i]/2+1);
	}
	deque<ll> q;
	FOR(i,1,N){
		// up[j]-j>=-i   up[j]-j>=-i  由于i的加入顺序是单调的，那自然肯定是单调栈
		while(q.empty()==false && up[i]-i<-q.front()){
			fib[q.front()]=i;
			q.pop_front();
		}
		q.pb(i);
	}
	
	q.clear();
	FOR(i,1,N){
		// up_j-j >= -i+A_i
		// 那么有一种方法那，就是这个单调栈维护的是-i+A_i的单调性，然后比up[i]-i大的-i+A_i
		// 全部被弹出来，那么其实如果up_j-j >= -i+A_i  那么A_j-j>=-i+A_i也成立
		while(q.empty()==false && up[i]-i<-q.back()+A[q.back()]){
			seb[q.back()]=i;
			q.pop_back();
		}
		q.pb(i);
	}
	ll ans=0;
	vector<ll> memo(N+5,0);		// 使用记忆化
	FOR(i,1,N){
		ll idx=fib[i],lab=idx-i;
		vector<ll> wp;
		bool isF=true;
		while(idx<=N){
			if(memo[idx]!=0 && isF==false){
				idx=memo[idx];
				ans+=idx-i+1;
				break;
			}
			isF=false;
			wp.pb(idx);
			if(A[idx]<lab){
				ans+=idx-i;
				idx-=1;
				break;
			}
			ll oidx=idx;
			idx=seb[idx];
			lab=idx-oidx+A[oidx];	// 从oidx以后增加的长度
			if(idx==N){
				if(A[idx]<lab){
					ans+=idx-i;
					idx-=1;
				}else{
					ans+=idx-i+1;
				}
				break;
			}
		}
		FOR(j,0,SZ(wp)-1){
			memo[wp[j]]=idx;
		}
#ifdef LOCAL
    debug(ans);
#endif
	}
// #ifdef LOCAL
    // FOR(i,1,N){
    	// cerr<<fib[i]<<" ";
    // }
    // cerr<<"\n";
    // FOR(i,1,N){
    	// cerr<<seb[i]<<" ";
    // }
    // cerr<<"\n";
// #endif
	cout<<ans<<"\n";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*

*/

心路历程（WA，TLE，MLE……）

TLE，应该是被卡了。就是像下面这样走有的时候可能会导致退化为线性时间复杂度。

FOR(i,1,N){
	ll idx=fib[i],lab=idx-i;
	while(idx<=N){
		// 
		if(A[idx]<lab){
			ans+=idx-i;
			break;
		}
		ll oidx=idx;
		idx=seb[idx];
		lab=idx-oidx+A[oidx];
		if(idx==N){
			if(A[idx]<lab){
				ans+=idx-i;
			}else{
				ans+=idx-i+1;
			}
			break;
		}
	}
}

源代码

// Problem: Sortable Subarrays (Hard)
// Contest: CodeChef - START189
// URL: https://www.codechef.com/problems/SORTSUB7?tab=statement
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e9)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN],up[MAXN],fib[MAXN],seb[MAXN];
/*

*/
inline void init(){
	FOR(i,1,N){
		fib[i]=N;
		seb[i]=N;
	}
}
inline void solve(){
	cin>>N;
	init();
	FOR(i,1,N){
		cin>>A[i];
	}
	// [\ 0,A_i \mod (A_i/2+1)\ ]
	FOR(i,1,N){
		up[i]=A[i]%(A[i]/2+1);
	}
	deque<ll> q;
	FOR(i,1,N){
		// up[j]-j>=-i   up[j]-j>=-i  由于i的加入顺序是单调的，那自然肯定是单调栈
		while(q.empty()==false && up[i]-i<-q.front()){
			fib[q.front()]=i;
			q.pop_front();
		}
		q.pb(i);
	}
	
	q.clear();
	FOR(i,1,N){
		// up_j-j >= -i+A_i
		// 那么有一种方法那，就是这个单调栈维护的是-i+A_i的单调性，然后比up[i]-i大的-i+A_i
		// 全部被弹出来，那么其实如果up_j-j >= -i+A_i  那么A_j-j>=-i+A_i也成立
		while(q.empty()==false && up[i]-i<-q.back()+A[q.back()]){
			seb[q.back()]=i;
			q.pop_back();
		}
		q.pb(i);
	}
	ll ans=0;
	FOR(i,1,N){
		ll idx=fib[i],lab=idx-i;
		while(idx<=N){
			// 
			if(A[idx]<lab){
				ans+=idx-i;
				break;
			}
			ll oidx=idx;
			idx=seb[idx];
			lab=idx-oidx+A[oidx];
			if(idx==N){
				if(A[idx]<lab){
					ans+=idx-i;
				}else{
					ans+=idx-i+1;
				}
				break;
			}
		}
	}
// #ifdef LOCAL
    // FOR(i,1,N){
    	// cerr<<fib[i]<<" ";
    // }
    // cerr<<"\n";
    // FOR(i,1,N){
    	// cerr<<seb[i]<<" ";
    // }
    // cerr<<"\n";
// #endif
	cout<<ans<<"\n";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*

*/

Starter190-MX PARR EZ/HARD

Posted on 2025-06-13 Edited on 2026-02-17

思路讲解

https://www.codechef.com/viewsolution/1165824691

简单的后缀最大判断。

困难版的题意稍微有点难懂，但是总的来说就是你不是找出来一个M吗，这个最大格挡序列可不可以包含i？

那么代码分析我放在这个链接里了，反正都是chinglish，都是读的懂的。

https://www.codechef.com/viewsolution/1166105552

那么正向的贪心操作怎么样复制到这个逆向那？我认为这个是这道题目比较值得学习的点。

ROF(i,N,1){
	if(opx+1>=B[i] && opx<X){
		opx++;
		++sans;
		suf[i]=sans;
		Ans[i]=true;
	}else{
		suf[i]=suf[i+1];
	}
}

AC代码

https://www.codechef.com/viewsolution/1165824691

EZ源代码

// Problem: Parry It! (Easy)  招架！（简单）
// Contest: CodeChef - START190
// URL: https://www.codechef.com/problems/MXPARREZ
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e9)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN],B[MAXN];
/*

*/
ll mxA[MAXN];
inline void init(){
	FOR(i,0,N+5){mxA[i]=0;}
}
inline void solve(){
	cin>>N>>X;
	init();
	FOR(i,1,N){
		cin>>A[i];
	}
	FOR(i,1,N){
		cin>>B[i];
	}
	ROF(i,N,1){
		mxA[i]=max(mxA[i+1],A[i]);
	}
	ll opx=X,ans=0;
	FOR(i,1,N){
		if(opx<A[i]){
			cout<<0<<"\n";
			return;
		}else if(opx>=B[i]){
			if(opx-1>=mxA[i+1]){
				opx--;
				++ans;
			}
		}
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC https://www.codechef.com/viewsolution/1165824691
*/

https://www.codechef.com/viewsolution/1166105552

HD源代码

// Problem: Parry It! (Hard)  招架！（困难）
// Contest: CodeChef - START190
// URL: https://www.codechef.com/problems/MXPARR
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e9)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN],B[MAXN];
/*

*/
ll mxA[MAXN],Xv[MAXN]; // smxA[MAXN];
ll suf[MAXN],pre[MAXN];
inline void init(){
	FOR(i,0,N+5){
		mxA[i]=0;
		// smxA[i]=0;
		suf[i]=0;
		pre[i]=0;
	}
}
inline void solve(){
	cin>>N>>X;
	init();
	FOR(i,1,N){
		cin>>A[i];
	}
	FOR(i,1,N){
		cin>>B[i];
	}
	ROF(i,N,1){
		mxA[i]=max(mxA[i+1],A[i]);
	}
	// FOR(i,1,N){smxA[i]=max(smxA[i-1],A[i]);}
	ll opx=X,ans=0,first=N;
	vector<bool> Ans(N+5,false);
	FOR(i,1,N){
		if(opx<A[i]){
			FOR(i,1,N)cout<<0;
			cout<<"\n";
			return;
		}else if(opx>=B[i]){
			if(opx-1>=mxA[i+1]){
				opx--;
				++ans;
				Ans[i]=true;
				first=min(first,(ll)i);
			}
		}
		pre[i]=ans;
		Xv[i]=opx;
	}
	if(ans==0){
		cout<<string(N,'0')<<"\n";
		return;
	}
// #ifdef LOCAL
   	// FOR(i,1,N){debug(i);debug(Xv[i]);}
// #endif
	opx=X-ans;ll sans=0;
	ROF(i,N,1){
		if(opx+1>=B[i] && opx<X){
			opx++;
			++sans;
			suf[i]=sans;
			Ans[i]=true;
		}else{
			suf[i]=suf[i+1];
		}
	}
	FOR(i,first+1,N){
		if(Ans[i]) continue;
		// if(B[i]<mxA[i+1]) continue;		// B[i]<mxA[i+1] 即会导致fail
		if(B[i]>X) continue;
		if(pre[i]>=ans-suf[i]-1){
			if(X-max((ll)0,ans-suf[i]-1)>=B[i]) Ans[i]=true;
		}
	}
#ifdef LOCAL
    debug(ans);
    debug(sans);
    FOR(i,1,N){
    	debug(i);
    	debug(suf[i]);
    }
    FOR(i,1,N){
    	debug(i);
    	debug(pre[i]);
    }
#endif
	FOR(i,1,N){
		cout<<Ans[i];
	}
	cout<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*
WA
https://www.codechef.com/viewsolution/1165848655
hack:
1
6 10
1 1 1 1 1 1
10 9 8 10 9 8
WA:111001
AC:111111


*/

心路历程（WA，TLE，MLE……）

Starter190-ORSUBSORT

Posted on 2025-06-13 Edited on 2026-02-17

思路讲解

codeChef题目可以看viewsolution，就是下面这个链接

inline ll diff(ll a,ll b){
	if(a<=b) return 0;
	bitset<32> ba(a);		// 存储是正序的
	bitset<32> bb(b);
	ROF(i,31,0){
		ll bai=ba[i],bbi=bb[i];
		if(bai-bbi==1){
			return 1<<i;
		}
	}
}

AC代码

https://www.codechef.com/viewsolution/1165814370

源代码

// Problem: Subsequence Sort
// Contest: CodeChef - START190
// URL: https://www.codechef.com/problems/ORSUBSORT
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e9)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
/*

*/
inline void init(){
	
}
inline ll diff(ll a,ll b){
	if(a<=b) return 0;
	bitset<32> ba(a);		// 存储是正序的
	bitset<32> bb(b);
	ROF(i,31,0){
		ll bai=ba[i],bbi=bb[i];
		if(bai-bbi==1){
			return 1<<i;
		}
	}
}
inline void solve(){
	cin>>N;
	init();
	FOR(i,1,N){
		cin>>A[i];
	}
	bool isSort=true;
	FOR(i,2,N){
		if(A[i-1]>A[i]){isSort=false;break;}
	}
	if(isSort){cout<<0<<"\n";return;}
	ll mxD=0,mx=A[1];
	FOR(i,2,N){
		mxD=max(mxD,diff(mx,A[i]));
		mx=max(mx,A[i]);
	}
	cout<<mxD<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://www.codechef.com/viewsolution/1165814370
*/

心路历程（WA，TLE，MLE……）

CF-1030-B. Make It Permutation

Posted on 2025-06-12 Edited on 2026-02-17

思路讲解

行上面反转，使列上面为排列。

注意到，可以对称的操作，反转1，i，使得 i 为首，再反转N-i+1，N，

// 第一阶段操作
// 对行 i = 1 到 n-1, 翻转子数组 [i, n]
for (int i = 1; i < n; ++i) {
    std::cout << i << " " << i << " " << n << std::endl;
}

// 第二阶段操作
// 对行 j = 2 到 n, 翻转子数组 [1, j-1]
// 为了让最终矩阵和上面推导的一致，我们倒序循环
for (int i = 1; i < n; ++i) {
    // 操作第 n-i+1 行， 翻转 [1, n-i]
    std::cout << (n - i + 1) << " " << 1 << " " << (n - i) << std::endl;
}

AC代码

源代码

#include <iostream>
#include <vector>
#include <numeric>

// 函数用于解决单个测试用例
void solve() {
    int n;
    std::cin >> n;

    // 总操作数是 (n-1) + (n-1) = 2n-2
    std::cout << 2 * n - 2 << std::endl;

    // 第一阶段操作
    // 对行 i = 1 到 n-1, 翻转子数组 [i, n]
    for (int i = 1; i < n; ++i) {
        std::cout << i << " " << i << " " << n << std::endl;
    }

    // 第二阶段操作
    // 对行 j = 2 到 n, 翻转子数组 [1, j-1]
    // 为了让最终矩阵和上面推导的一致，我们倒序循环
    for (int i = 1; i < n; ++i) {
        // 操作第 n-i+1 行， 翻转 [1, n-i]
        std::cout << (n - i + 1) << " " << 1 << " " << (n - i) << std::endl;
    }
}

int main() {
    // 优化输入输出
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

// AC