题目
CF1156E Special Segments of Permutation
分析
分治，单调栈，笛卡尔树。
分治经典套路了，像这样数点对的都可以考虑分治。（树上就考虑点分治）
同样是经典套路，每次分治时钦定一定是右侧存在最大值或者左侧存在最大值。
然后双指针和一个数组统计即可，具体见代码。
这样的极长最值区间的问题其实也可以考虑单调栈和笛卡尔树，具体见题解吧。
代码
分治代码。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define inc(x,y,mod) (((x)+(y))>=(mod)?(x)+(y)-(mod):(x)+(y))
#define dec(x,y,mod) ((x)-(y)<0?(x)-(y)+(mod):(x)-(y))
#define rep(i,x,y) for(int i=(x);i<=(y);i++)
#define dep(i,y,x) for(int i=(y);i>=(x);i--)
const int N=2e5+5,M=2e5+5,MOD=1e9+7;
int n,m,a[N],Ans;
bool t[N];
void Solve(int l,int r){
if(l==r) return ;
int mid=l+r>>1;
Solve(l,mid),Solve(mid+1,r);
int pos=mid,Maxn=0;
for(register int i=mid+1;i<=r;i++){
Maxn=max(Maxn,a[i]);
while(pos>=l&&a[pos]<=Maxn) t[a[pos]]=true,pos--;
Ans+=t[Maxn-a[i]];
}
for(register int i=l;i<=mid;i++) t[a[i]]=false;
pos=mid+1,Maxn=0;
for(register int i=mid;i>=l;i--){
Maxn=max(Maxn,a[i]);
while(pos<=r&&a[pos]<=Maxn) t[a[pos]]=true,pos++;
Ans+=t[Maxn-a[i]];
}
for(register int i=mid+1;i<=r;i++) t[a[i]]=false;
return ;
}
signed main(){
ios::sync_with_stdio(false);
cin>>n;
rep(i,1,n) cin>>a[i];
Solve(1,n);
cout<<Ans;
return 0;
}