定义
-
排列：由 \(1\sim n\) 打乱组成的序列。
-
连续段：\([l,r]\) 被称为连续段，当且仅当排列 \(a\) 中 \(a_{l...r}\) 在排序后值域也连续。
构想
析合树是一种处理排列连续段问题的有力数据结构。
但是一个排列的连续段数可能达到 \(O(n^2)\)，我们该如何存储？
一些连续段可能会与其他连续段严格相交，我们称这些连续段为非本原连续段。
其他连续段称为本原连续段，简称本原段。
我们可以证明，一个排列的本原段个数不超过 \(O(n)\)，于是我们考虑只存储本原段。
一个本原段可能由多个本原段组成，所以我们采用树形结构存储。
每个结点表示一个本原段。若他不是叶子，那么他是由儿子对应的本原段从左到右连接而成的。
析合树
析合树是一种符合我们构想的一种树，他将上面的结点分为了两类：析点、合点。在这里，我们不讨论叶子的分类。
-
合点：一个结点是合点，当且仅当他的儿子本原段也是有序的，可以是从小到大，也可以是从大到小。例如：\([1,10]=[1,3]+[4,5]+[6,9]+[10,10]\)。
-
析点：不是合点的点就是析点。例如：\([1,10]=[6,9]+[1,3]+[10,10]+[4,5]\)。
定义子连续段为一个点的连续几个儿子组成的非本原连续段。
-
定理：析点的儿子无法组成子连续段。
-
证明：反证法，假设有一段儿子组成了子连续段，那么不存在其他连续段与这个子连续段严格相交。根据定义，这些儿子会合并成一个合点，矛盾。
构建
这里使用增量法。
维护一个栈，存储一棵析合树森林。
加入 \(a_i\)，我们令 \(now\) 为新的结点，分情况：
- 栈顶不是叶子，且 \(now\) 可以作为栈顶的儿子。
此时栈顶一定不是析点，否则会存在子连续段，所以一定是合点。
我们还需要判断接为栈顶儿子后栈顶是否仍然是合点，额外记录 \(M_u\) 表示点 \(u\) 最右边的儿子的左端点，判断 \([M_u,i]\) 是否为连续段即可。
最后把栈顶作为新的 \(now\)。
- 与栈顶并列，形成一个合点，作为父亲。
判断两者是否形成一个连续段即可，然后把合点作为 \(now\)。
- 与栈顶部若干个点一同并列，形成一个析点，作为父亲。
我们不断弹出栈顶，并判断是否已经形成一个连续段，若已经形成则退出。然后把析点作为 \(now\)。
每次还需要判断 \(now\) 是否还能与先前本原段合并，我们需要支持查找可以合并到的最早的位置，可以用 这题 的线段树完成。
这里放一下 CF 的图。
我们要用一个 ST 表、一个线段树、三个栈，时间复杂度 \(O(n\log n)\)。当然你愿意的话，可以试试学 \(O(n)\) 的析合树。
点击查看代码
#define ll long long
#define pb push_back
using namespace std;
const ll maxn=2e5+10;
ll n,a[maxn];
struct RMQ{
ll st_min[20][maxn], st_max[20][maxn], Log[maxn];
void build(){
for(ll i=2;i<=n;i++) Log[i]=Log[i>>1]+1;
for(ll i=1;i<=n;i++) st_min[0][i]=st_max[0][i]=a[i];
for(ll i=1;(1<<i)<=n;i++)
for(ll j=1;j+(1<<i)-1<=n;j++)
st_min[i][j]=min(st_min[i-1][j],st_min[i-1][j+(1<<i-1)]),
st_max[i][j]=max(st_max[i-1][j],st_max[i-1][j+(1<<i-1)]);
}
ll qry_min(ll l,ll r){
ll k=Log[r-l];
return min(st_min[k][l],st_min[k][r-(1<<k)+1]);
}
ll qry_max(ll l,ll r){
ll k=Log[r-l];
return max(st_max[k][l],st_max[k][r-(1<<k)+1]);
}
}D;
struct SGT{
ll tag[maxn<<2], mn[maxn<<2], pos[maxn<<2];
void addtag(ll p,ll v){
tag[p]+=v, mn[p]+=v;
}
void pushdown(ll p){
addtag(p<<1,tag[p]), addtag(p<<1|1,tag[p]);
tag[p]=0;
}
void modify(ll p,ll l,ll r,ll ql,ll qr,ll v){
if(ql<=l&&r<=qr) {addtag(p,v); return;}
pushdown(p); ll mid=l+r>>1;
if(ql<=mid) modify(p<<1,l,mid,ql,qr,v);
if(mid<qr) modify(p<<1|1,mid+1,r,ql,qr,v);
mn[p]=min(mn[p<<1],mn[p<<1|1]);
if(mn[p]==mn[p<<1]) pos[p]=pos[p<<1];
else pos[p]=pos[p<<1|1];
}
void build(ll p,ll l,ll r){
pos[p]=l;
if(l==r) return;
ll mid=l+r>>1;
build(p<<1,l,mid), build(p<<1|1,mid+1,r);
}
}T;
ll chk(ll l,ll r) {return D.qry_max(l,r)-D.qry_min(l,r)-(r-l)==0;}
ll stk_min[maxn],top_min,stk_max[maxn],top_max;
ll stk[maxn],top,typ[maxn<<1],L[maxn<<1],R[maxn<<1],M[maxn<<1],cnt,id[maxn];
vector<ll>to[maxn<<1];
void build(){
D.build();
T.build(1,1,n);
for(ll i=1;i<=n;i++){
while(top_min&&a[stk_min[top_min]]>a[i])
T.modify(1,1,n,stk_min[top_min-1]+1,stk_min[top_min],a[stk_min[top_min]]), --top_min;
while(top_max&&a[stk_max[top_max]]<a[i])
T.modify(1,1,n,stk_max[top_max-1]+1,stk_max[top_max],-a[stk_max[top_max]]), --top_max;
T.modify(1,1,n,stk_min[top_min]+1,i,-a[i]);
T.modify(1,1,n,stk_max[top_max]+1,i,a[i]);
stk_min[++top_min]=i, stk_max[++top_max]=i;
id[i]=++cnt, L[cnt]=R[cnt]=i;
ll now=cnt;
while(top&&L[stk[top]]>=T.pos[1]){
if(typ[stk[top]]&&chk(M[stk[top]],i)){
to[stk[top]].pb(now);
R[stk[top]]=i, M[stk[top]]=L[now], now=stk[top];
--top;
} else if(chk(L[stk[top]],i)){
++cnt, typ[cnt]=1;
L[cnt]=L[stk[top]], R[cnt]=i, M[cnt]=L[now];
to[cnt].pb(stk[top]), to[cnt].pb(now);
now=cnt, --top;
} else{
++cnt, to[cnt].pb(now);
do to[cnt].pb(stk[top--]);
while (top&&!chk(L[stk[top]],i));
L[cnt]=L[stk[top]], R[cnt]=i, to[cnt].pb(stk[top]);
now=cnt, --top;
}
} stk[++top]=now;
T.modify(1,1,n,1,i,-1);
}
}