析合树

liucr · 2024-10-30 11:47:28 · 算法·理论

前置知识：

ST 表。
线段树。
单调栈。

析合树 板子题。

本篇的图片来自 codeforces。

给定长度 n 的排列，求区间个数，使得区间内所有数排序后相邻数字相差均为 1。

抛两个定义：

连续段，对于排列的一段，段内所有数排序后相邻数字相差均为 1，则称其为连续段，如同题意。
本原连续段，对于一个连续段 [l,r]，如果不存在另外一个连续段 [l',r'] 使得 l\in[l',r'] 和 r\in[l',r'] 有且仅有一个成立，则称 [l,r] 为本原连续段。l=r 时，[l,r] 为本原连续段。

可以很容易地发现，任意两个本原连续段 A,B，要么 A 包含 B，要么 B 包含 A，要么 A,B 无交集。

如图，将每个本原连续段作为节点建造一棵这样的树，本原连续段节点按照区间的形式给出，此为析合树。

再抛四个定义：

儿子序列：析合树上一个节点的每个儿子节点按照原数组顺序依次构成的序列。
儿子排列：析合树上一个节点的儿子序列依据值域左端排序后的每个排行。
合点：儿子排列正序或倒序的节点，为了方便，叶子不是合点。
析点：非合点即析点。

根据定义，合、析点具有以下性质：

合点的儿子序列集合的任意严格连续（长度 \geq2 的）子集都是连续段，析点则都不是（若存在，则会将其合并为新的合点）。
析点最少具有四个儿子节点。

接下来是析合树的构造。

考虑使用一个栈，假设 1\sim i-1 的元素已经插入完毕，栈顶是 top，考虑 i 的情况：

- $top$ 是**合点**，且 $a_i$ 作为 $top$ 的儿子之后 $top$ 仍然是**合点**，将 $a_i$ 作为 $top$ 儿子，取出并重新往栈中加入 $top$ 继续这个过程。 - 反之，新建一个节点 $new$，将 $top$ 与 $a_i$ 作为其儿子，取出并重新往栈中加入 $new$ 继续这个过程。
- 若可以，新建一个节点 $new$ 与 $stk[l]\sim top$ 和 $a_i$ 连边，此时 $new$ 为**析点**。 - 反之，直接在栈中加入 $a_i$。

但是找到这个 l 的复杂度可能退化成 \Theta(n^2)，需要优化。

考虑记录一个 L_i 表示 [x,i] 为连续段的最小 x。

实际上，一段 [l,r] 是否为连续段，意味着 \max-\min=r-l，即极差为区间长度 -1。通过移项可以得到 \max-\min+(l-r)=0，而显然 \max-\min+(l-r)\geq0，故求 L_i 相当于求 \max-\min+(l-r) 最左端最小值的下标。

记录一个 Q_j，表示 [j,i] 范围内的 \max-\min+(l-r)。求 L_i 相当于求最左端的最小 Q_j 的下标。

现在假设要从枚举的右端点 i 转到 i+1，那么需要对三个量进行修改：\max,\min 以及区间长度。

对于 \max，如果 [j,i+1] 的 \max 是 a_{i+1}，则 Q_j 原来的 \max 也同时改变，将 Q_j 减去原来的 \max 并加上 a_{i+1}。实际上，找到最右端的点 x 使得 x<i+1 且 [x+1\sim i,i+1] 的 \max 是 a_{i+1}，然后对于 [x+1,i] 中每段具有相同 \max 的部分，整段修改 Q_i。
对于 \min，同理。
对于区间长度，Q_{1\sim i} 的区间长度都要加一，这很显然。

可以考虑单调栈维护一个 D_i 表示比 a_i 大的最右端的 j 满足 j<i（不存在，则默认 D_i=0）。这可以快速求出最右端的点 x 使得 x<i+1 且 [x+1\sim i,i+1] 的 \max 是 a_{i+1}，以及快速地跳 [x+1,i] 的每段具有 \max 部分。\min 同理。

对于一段的加操作以及求 \min 所在下标，考虑数据结构维护，一般采取线段树（线段树怎么搞想必都会），均摊复杂度后可以达到 \Theta(n\log n) 的预处理复杂度。建树的复杂度均摊后为 \Theta(n)。

对于板子题。显然可以把矩阵转换序列，对于每个有怪物的节点 (i,j)，令 a_i=j，然后对 a 求连续段个数。

显然，对于每个合点，儿子序列构成的所有连续子集（包含儿子个数需要 \geq2，否则贡献会与儿子的重复）都加一点贡献，且注意 l<r，故假设合点儿子个数 s，则该合点贡献为 \frac{s(s-1)}{2}。对于每个析点，儿子序列构成所有严格连续子集都不合法，而其本身合法，贡献 1。

综上所述，构造完析合树之后直接计数即可。

这里感谢 @__er 和 @tbdsh 做出了一些帮助。

#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
    int res=0,f=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {res=res*10+(c-'0');c=getchar();}
    return res*f;
}
const int N=3e5+5;
int n,a[N],L[N],Q[N<<1],LOG[N],T[N<<1];
vector<int>son[N<<1],mode;
struct Stack{//手写栈
    int tip,Stk[N<<1];
    void push(int x) {Stk[++tip]=x;}
    int top() {return Stk[tip];}
    void pop() {tip--;}
    int size() {return tip;}
    bool empty() {return !tip;}
    int get(int x) {return Stk[x];}
    void clear() {tip=0;}
}s1,s2,s;
struct dot{
    int l,r,tmp;
}d[N<<1];
struct ST{//ST 表，区间求最值
    #define k LOG[r-l+1]
    int fax[N][25],fin[N][25];
    void build(){//O(n log n)
        for (int i=1;i<=n;++i) fax[i][0]=fin[i][0]=a[i];
        for (int j=1;j<25;++j)
            for (int i=1;i+(1<<j)-1<=n;++i){
                fax[i][j]=max(fax[i][j-1],fax[i+(1<<(j-1))][j-1]);
                fin[i][j]=min(fin[i][j-1],fin[i+(1<<(j-1))][j-1]);
            }
        for (int i=2;i<=N-5;i++) LOG[i]=LOG[i>>1]+1;
    }
    bool query(int l,int r){//O(1)
        return (max(fax[l][k],fax[r-(1<<k)+1][k])-min(fin[l][k],fin[r-(1<<k)+1][k])==r-l);
    }
    #undef k
}st;
struct sgm{//线段树
    #define lc (x<<1)
    #define rc (x<<1|1)
    int tag[N<<2],mn[N<<2],ans[N<<2];
    void push_up(int x){//O(1)
        mn[x]=min(mn[lc],mn[rc]);
        ans[x]=ans[lc]+ans[rc];
    }
    void push_down(int x){//O(1)
        if (!tag[x]) return;
        tag[lc]+=tag[x],tag[rc]+=tag[x];
        mn[lc]+=tag[x],mn[rc]+=tag[x];
        tag[x]=0;
    }
    void update(int x,int l,int r,int ql,int qr,int d){//O(log n)
        if (ql>qr) return;
        if (ql<=l&&qr>=r){
            tag[x]+=d,mn[x]+=d,ans[x]+=d;
            return;
        }
        push_down(x);
        int mid=(l+r)>>1;
        if (ql<=mid) update(lc,l,mid,ql,qr,d);
        if (qr>mid) update(rc,mid+1,r,ql,qr,d);
        push_up(x);
    }
    int query(int x,int l,int r){//O(log n)
        if (l==r) return l;
        push_down(x);
        int mid=(l+r)>>1;
        if (!mn[lc]) return query(lc,l,mid);
        else return query(rc,mid+1,r);
    }
    #undef lc
    #undef rc
}book;
void Init(){//O(n log n)
  //这里是初始化 L 数组用的函数
    for (int i=1;i<=n;++i){
        while (!s1.empty()&&a[i]<=a[s1.top()]){
            int x=s1.top();
            s1.pop();
            book.update(1,1,n,s1.top()+1,x,a[x]);
        }
        while (!s2.empty()&&a[i]>=a[s2.top()]){
            int x=s2.top();
            s2.pop();
            book.update(1,1,n,s2.top()+1,x,-a[x]);
        }
        book.update(1,1,n,s1.top()+1,i,-a[i]);
        book.update(1,1,n,s2.top()+1,i,a[i]);
        s1.push(i),s2.push(i);
        L[i]=book.query(1,1,n);
        book.update(1,1,n,1,i,-1);
    }
//  for (int i=1;i<=n;i++) cout<<L[i]<<' ';cout<<'\n';
}
int cnt;
void Build_Tree(){//O(n)
  //建立析合树
    for (int i=1;i<=n;i++){
        d[++cnt]={i,i,0};
        int now=cnt;
        while (!s.empty()&&d[s.top()].l>=L[i]){
            int x=s.top();
            if (d[x].tmp&&st.query(T[x],i)){
                d[x].r=i,T[x]=d[now].l,son[x].push_back(now);
                now=x,s.pop();
            }
            else if (st.query(d[x].l,i)){
                d[++cnt]={d[x].l,d[now].r,1};
                son[cnt].push_back(x),son[cnt].push_back(now);
                T[cnt]=d[now].l,now=cnt,s.pop();
            }
            else{
                do{
                    mode.push_back(s.top());
                    s.pop();
                }
                while (!s.empty()&&!st.query(d[s.top()].l,i));
                d[++cnt]={d[s.top()].l,i,0};
                son[cnt].push_back(s.top());
                for (auto v:mode) son[cnt].push_back(v);
                son[cnt].push_back(now),now=cnt;
                s.pop(),mode.clear();
            }
        }
        s.push(now);
//      cout<<d[s.top()].l<<' '<<d[s.top()].r<<'\n';
    }
}
signed main(){
    n=read();
    for (int i=1;i<=n;++i){
        int __=read();
        a[__]=read();
    }
    Init(),st.build();
    Build_Tree();
    int ans=0;
    for (int i=1;i<=cnt;++i){//O(n)
//      cout<<d[i].l<<' '<<d[i].r<<'\n';
        if (d[i].tmp){
            int x=son[i].size();
            ans+=x*(x-1)>>1;//计算答案，建树后过程并不复杂
        }
        else ans++;
    }
    cout<<ans;
    return 0;
}

例题：P4747，析合树的基础运用。

我们考虑对排列建出析合树。

对于给定的区间 [l,r]，不难发现包含 [l,r] 的最短本原连续段即析合树上 [l,l] 与 [r,r] 对应节点的 \text{lca}，且是唯一的。这个很显然，因为关于本排列的所有本原连续段要么互相包含，要么互无交集。

那么需要考虑通过本原连续段 [a,b] 找到答案，可以分类讨论处理：

如果 [a,b] 对应节点是析点，因为析点儿子序列所有长度 \geq2 的严格子段均不为连续段，且如果可以找到长度 =1 的连续段，那么 [a,b] 就不可能为 [l,l] 和 [r,r] 的 \text{lca}。故不存在儿子序列的严格子段为答案，答案只能是 [a,b]。
如果是合点，可以在排序后的儿子序列上二分，令 a' 为儿子序列从右往左第一个满足左端点 \leq a 的儿子的左端点，b' 为儿子序列从左往右第一个满足右端点 \geq b 的儿子的右端点。显然，a',b' 可以二分，答案为 [a',b']。

时间复杂度 \Theta(n\log n)。

#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
    int res=0,f=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {res=res*10+(c-'0');c=getchar();}
    return res*f;
}
const int N=1e5+5;
int n,a[N],L[N],Q[N<<1],LOG[N],T[N<<1],dz[N];
vector<int>son[N<<1],mode;
struct Stack{
    int tip,Stk[N];
    void push(int x) {Stk[++tip]=x;}
    int top() {return Stk[tip];}
    void pop() {tip--;}
    int size() {return tip;}
    bool empty() {return !tip;}
    int get(int x) {return Stk[x];}
    void clear() {tip=0;}
}s1,s2,s;
struct dot{
    int l,r,tmp;
}d[N<<1];
struct ST{
    #define k LOG[r-l+1]
    int fax[N][17],fin[N][17];
    void build(){//O(n log n)
        for (int i=1;i<=n;i++) fax[i][0]=fin[i][0]=a[i];
        for (int j=1;j<17;j++)
            for (int i=1;i+(1<<j)-1<=n;i++){
                fax[i][j]=max(fax[i][j-1],fax[i+(1<<(j-1))][j-1]);
                fin[i][j]=min(fin[i][j-1],fin[i+(1<<(j-1))][j-1]);
            }
        for (int i=2;i<=N-5;i++) LOG[i]=LOG[i>>1]+1;
    }
    bool query(int l,int r){//O(1)
        return (max(fax[l][k],fax[r-(1<<k)+1][k])-min(fin[l][k],fin[r-(1<<k)+1][k])==r-l);
    }
    #undef k
}st;
struct sgm{
    #define lc (x<<1)
    #define rc (x<<1|1)
    int tag[N<<2],mn[N<<2],ans[N<<2];
    void push_up(int x){//O(1)
        mn[x]=min(mn[lc],mn[rc]);
        ans[x]=ans[lc]+ans[rc];
    }
    void push_down(int x){//O(1)
        if (!tag[x]) return;
        tag[lc]+=tag[x],tag[rc]+=tag[x];
        mn[lc]+=tag[x],mn[rc]+=tag[x];
        tag[x]=0;
    }
    void update(int x,int l,int r,int ql,int qr,int d){//O(log n)
        if (ql>qr) return;
        if (ql<=l&&qr>=r){
            tag[x]+=d,mn[x]+=d,ans[x]+=d;
            return;
        }
        push_down(x);
        int mid=(l+r)>>1;
        if (ql<=mid) update(lc,l,mid,ql,qr,d);
        if (qr>mid) update(rc,mid+1,r,ql,qr,d);
        push_up(x);
    }
    int query(int x,int l,int r){//O(log n)
        if (l==r) return l;
        push_down(x);
        int mid=(l+r)>>1;
        if (!mn[lc]) return query(lc,l,mid);
        else return query(rc,mid+1,r);
    }
    #undef lc
    #undef rc
}book;
void Init(){//O(n log n)
    for (int i=1;i<=n;i++){
        while (!s1.empty()&&a[i]<=a[s1.top()]){
            int x=s1.top();
            s1.pop();
            book.update(1,1,n,s1.top()+1,x,a[x]);
        }
        while (!s2.empty()&&a[i]>=a[s2.top()]){
            int x=s2.top();
            s2.pop();
            book.update(1,1,n,s2.top()+1,x,-a[x]);
        }
        book.update(1,1,n,s1.top()+1,i,-a[i]);
        book.update(1,1,n,s2.top()+1,i,a[i]);
        s1.push(i),s2.push(i);
        L[i]=book.query(1,1,n);
        book.update(1,1,n,1,i,-1);
    }
//  for (int i=1;i<=n;i++) cout<<L[i]<<' ';cout<<'\n';
}
int cnt;
void Build_Tree(){//O(n)
    for (int i=1;i<=n;i++){
        d[++cnt]={i,i,0};
        int now=cnt;
        while (!s.empty()&&d[s.top()].l>=L[i]){
            int x=s.top();
            if (d[x].tmp&&st.query(T[x],i)){
                d[x].r=i,T[x]=d[now].l,son[x].push_back(now);
                now=x,s.pop();
            }
            else if (st.query(d[x].l,i)){
                d[++cnt]={d[x].l,d[now].r,1};
                son[cnt].push_back(x),son[cnt].push_back(now);
                T[cnt]=d[now].l,now=cnt,s.pop();
            }
            else{
                do{
                    mode.push_back(s.top());
                    s.pop();
                }
                while (!s.empty()&&!st.query(d[s.top()].l,i));
                d[++cnt]={d[s.top()].l,i,0};
                son[cnt].push_back(s.top());
                for (auto v:mode) son[cnt].push_back(v);
                son[cnt].push_back(now),now=cnt;
                s.pop(),mode.clear();
            }
        }
        s.push(now);
//      cout<<d[s.top()].l<<' '<<d[s.top()].r<<'\n';
    }
}
vector<int>e[N<<1];
int dep[N<<1],siz[N<<1],fa[N<<1],Bson[N<<1];
int dfs(int u,int father){
    dep[u]=dep[father]+1;
    fa[u]=father;
    siz[u]=1;
    int maxn=-1;
    for (auto v:e[u]){
        if (v==father) continue;
        int sizes=dfs(v,u);
        siz[u]+=sizes;
        if (sizes>maxn) maxn=sizes,Bson[u]=v;
    }
    return siz[u];
}
int dfn[N<<1],top[N<<1],tip=1;
void dfs2(int u,int father,int op){
    if (op==1) top[u]=top[father];
    dfn[u]=tip++;
    if (Bson[u]!=0) dfs2(Bson[u],u,1);
    for (auto v:e[u]){
        if (v==father||v==Bson[u]) continue;
        dfs2(v,u,0);
    }
}
void init(int root){
    dfs(root,0);
    for (int i=1;i<=n;i++) top[i]=i;
    dfs2(root,0,0);
}
int lca(int x,int y){
    if (top[x]==top[y]) return dep[x]>dep[y]?y:x;
    if (dep[top[x]]<dep[top[y]]) swap(x,y);
    return lca(fa[top[x]],y);
}
signed main(){
    n=read();
    for (int i=1;i<=n;i++){
        int __=i;
        a[__]=read();
    }
    Init(),st.build();
    Build_Tree();
    int rt=0;
    for (int i=1;i<=cnt;i++){
        if (d[i].l==1&&d[i].r==n) rt=i;
        if (d[i].l==d[i].r) dz[d[i].l]=i;
        for (auto j:son[i]){
            e[i].push_back(j);
            e[j].push_back(i);
//          cout<<d[i].l<<','<<d[i].r<<' '<<d[j].l<<','<<d[j].r<<'\n';
        }
    }
    n=cnt,init(rt);
    int Qr=read();
    while (Qr--){//与模板不同的是，这里的求答案较为复杂，但事实上不难
        int dl=read(),dr=read(),_lca=lca(dz[dl],dz[dr]);
        if (!d[_lca].tmp){
            cout<<d[_lca].l<<' '<<d[_lca].r<<'\n';
            continue;
        }
        int _l=0,_r=son[_lca].size()-1,t1,t2;
        while (_l<_r){
            int mid=(_l+_r+1)>>1,x=son[_lca][mid];
            if (d[x].l<=dl) _l=mid;
            else _r=mid-1;
        }
        t1=son[_lca][_l],_l=0,_r=son[_lca].size()-1;
        while (_l<_r){
            int mid=(_l+_r)>>1,x=son[_lca][mid];
            if (d[x].r>=dr) _r=mid;
            else _l=mid+1;
        }
        t2=son[_lca][_l];
        cout<<d[t1].l<<' '<<d[t2].r<<'\n';
    }
    return 0;
}

当然，析合树考的可能比较灵活，比如 CF1089I，一道运用其思想的好题。

对排列构建出析合树之后，题意可以被转化为：求使得析合树的节点个数为 n+1 的排列个数。

记录一个 ans_i 表示 n=i 对应的答案，这样每次询问都是 \Theta(1) 的，考虑如何预处理。

根据题意，析合树节点个数 n+1，意味着根节点有 n 个儿子，且这些儿子全部为叶子节点。正难则反，利用容斥可以把答案改为：排列个数（显然是 n!），减去根为合点的方案数，减去根为析点但是根的儿子个数 <n 的方案数。

对于根为合点情况，根据合点性质，存在一个排列的前缀使得其为值域 [1,i] 的连续段。考虑记录一个 f_i 表示对于一个长度为 i 的排列，其任何一个前缀都不是是值域为 [1,i] 的连续段的方案数。

对于根为析点的情况，因为析点儿子数量 $\geq4$，故可以假设根的儿子为 $i$ 个，每个儿子是连续段，但是儿子排列不存在长度 $\geq2$ 的**严格子段**连续段。设 $g_{i,j}$ 表示把 $i$ 个数划分到 $j$ 个儿子的方案数，显然，枚举最后一个儿子包含数的数量 $k$，有 $g_{i,j}=\sum_{k=1}^{i-1}g_{i-k,j-1}k!$。而该部分答案为 $\sum_{j=4}^{n-1}ans_j\cdot g_{n,j}$，其中 $ans_j$ 是对儿子排列的结果。特判一下 $n=1,2,3$ 时答案分别为 $1,2,0$，原因显然，其余情况最终答案即为 $n!-\sum_{j=1}^{n-1}f_j(n-j)!-\sum_{j=4}^{n-1}ans_j\cdot g_{n,j}$。 ```cpp #include <bits/stdc++.h> using namespace std; #define int long long #define fr first #define sc second inline int read(){ int res=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') {res=res*10+(c-'0');c=getchar();} return res*f; } const int N=405; int T,M,n,fac[N],f[N],g[N][N],ans[N]; signed main(){ T=read(),M=read(); fac[0]=1,g[0][0]=1; for (int i=1;i<=N-5;i++){ f[i]=fac[i]=fac[i-1]*i%M; for (int j=1;j<=i;j++){ for (int k=1;k<=i;k++){ g[i][j]+=g[i-k][j-1]*fac[k]%M; g[i][j]%=M; } if (!(j^i)) continue; f[i]-=f[j]*fac[i-j]%M; f[i]=(f[i]%M+M)%M; } } ans[1]=1,ans[2]=2; for (int i=4;i<=N-5;i++){ ans[i]=fac[i]; for (int j=1;j<i;j++){ ans[i]-=(f[j]*fac[i-j]%M)*2%M; ans[i]=(ans[i]%M+M)%M; if (j<=3) continue; ans[i]-=g[i][j]*ans[j]%M; ans[i]=(ans[i]%M+M)%M; } } while (T--){ int n=read(); cout<<ans[n]<<'\n'; } return 0; } ``` 此篇结。