笛卡尔树分治(启发式分裂)
cpp
int a[N],n,stk[N],ls[N],rs[N],top;
void dfs(int u,int l,int r){
if(l>=r){
//操作叶节点
return;
}
int len=a[u];
if(u-l+1>=r-u+1){
//操作右边
}
else{
//操作左边
}
if(ls[u])dfs(ls[u],l,u-1);
if(rs[u])dfs(rs[u],u+1,r);
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int cur=0;
for(int i=1;i<=n;i++){
cur=top;
while(cur&&a[stk[cur]]<a[i])cur--;
if(cur)rs[stk[cur]]=i;
if(cur<top)ls[i]=stk[cur+1];
stk[++cur]=i;
top=cur;
}
dfs(stk[1],1,n);
cout<<ans<<"\n";
}