Starter189-Sortable Subarrays (Easy/Hard)

思路讲解

就是问可以通过$ 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;
}
/*

*/