Starter189-Sortable Subarrays (Easy/Hard) · znzryb
## 思路讲解
就是问可以通过$ A_i=A_i \mod X$ 这个操作变的有序的子串有多少个？
那么注意到那，这个操作没有说那么不可控，其实就是可以变为$[\ 0,A_i \mod (A_i/2+1)\ ]$ 中的一个。
[https://www.codechef.com/viewsolution/1166421088](https://www.codechef.com/viewsolution/1166421088)
```cpp
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](https://www.codechef.com/viewsolution/1166421088)
::: 源代码
```cpp
// 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](https://www.codechef.com/viewsolution/1166895091)
::: 源代码
```cpp
// 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，应该是被卡了。就是像下面这样走有的时候可能会导致退化为线性时间复杂度。
```cpp
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;
}
}
}
```
::: 源代码
```cpp
// 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;
}
/*
*/
```
:::