析合树是一种解决连续段问题的数据结构。

比如这样的一个问题：给你一个\(1\)到\(n\)的排列，然后有一堆询问，每次询问区间\([l,r]\)，问包含\([l,r]\)的最小连续段是什么。

也就是

所谓的连续段，就是满足\(max_{l..r}-min_{l..r}+1=r-l+1\)的连续段。

---

推荐这篇：

里面有比较系统的介绍。

虽然没有线性的构造方法

---

关于析合树，有各种各样的定义和性质，那些东西就是叫人看不懂的……。

所以我在这里就简单地说一说。

先说个性质：对于两个连续段\([l_1,r_1]\)和\([l_2,r_2]\)

如果它们有交集（即\([l_2,r_1]\)），则交集也是连续段。

并且它们的并集也是连续段。

这个不用解释吧……

---

有一个叫本源连续段的概念，不过具体指什么，我也不太懂……所以就不说了……

估计学到差不多的时候看字面意思就知道是什么东西了……

盗张图来瞅一瞅。

析合树的每个点都表示一个连续段，确切地说，是本源连续段。

析合树有两种点：析点和合点。

析点满足所有相邻儿子都不能合并成个连续段，合点满足所有相邻儿子都能合并成个连续段（可以看成儿子都是顺序或倒序的）。

有个很显然的性质是，析点至少有四个节点，合点至少有两个节点。

至于最下面的叶子结点就不要管了……程序实现时为了方便我会将其设为析点。

如果建出了析合树，前面的那个问题就有的答案：求出两个点的\(LCA\)，如果是析点，则就是析点代表的区间。如果是合点，则就是\(l\)和\(r\)的祖先在\(LCA\)下的儿子之间组成的区间。

---

接下来就是最重要的问题：如何建析合树。

建析合树用的是增量法，也就是一个一个点加进去。

维护一个栈，表示目前形成的森林的根节点。

假设加进去的点为\(x\)，栈顶为\(top\)。

1. \(top\)为合点，并且\(top\)的最后一个儿子可以和\(x\)合并。这个时候就直接将\(x\)作为\(top\)的儿子，然后将\(top\)递归下去继续干。
2. \(top\)和\(x\)可以合并。新建一个合点，作为\(top\)和\(x\)的父亲，然后将它们的父亲递归下去。
3. 往前面找若干个节点，满足这若干个节点和\(x\)可以合并。然后新建一个析点，将这些点都作为它的儿子，然后将它递归下去。
4. 若栈为空，或者第三个操作没有找到，\(x\)节点就加入栈顶。

---

然而直接这样建树是\(O(n^2)\)的。上面第三个操作的时候可能一直往前找都找不到，那这样一次就是\(O(n)\)的了。

考虑直接在这方面优化。一个简单的思路是求出\(L_i\)，表示\([L_i,i]\)以\(i\)为右端点的最长的连续段。

这样在第三个操作的时候就能够明确最多找到哪里，并且，最后面这些节点全部都会合并起来，栈顶的节点就是\([L_i,i]\)

问题转化成了如何求\(L_i\)

看看。用那个线段树的做法就行了。

大体思路就是维护两个单调栈，然后在线段树上维护。

求出了\(L_i\)，那么建树的时间复杂度就是\(O(n)\)的了。

可惜预处理需要\(O(n \lg n)\)的时间来预处理。

放个代码：

using namespace std;#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define N 100010int n,a[N];int smn[N],smx[N],tn,tx;int mn[N*4],tag[N*4];int L[N];inline void pushdown(int k){    if (tag[k]){        mn[k<<1]+=tag[k],mn[k<<1|1]+=tag[k];        tag[k<<1]+=tag[k],tag[k<<1|1]+=tag[k];        tag[k]=0;    }}void add(int k,int l,int r,int st,int en,int c){    if (st<=l && r<=en){        mn[k]+=c;        tag[k]+=c;        return;    }    pushdown(k);    int mid=l+r>>1;    if (st<=mid)        add(k<<1,l,mid,st,en,c);    if (mid
        
         v)        return 0;    if (l==r)        return l;    pushdown(k);    int mid=l+r>>1,res=0;    if (st<=mid)        res=find(k<<1,l,mid,st,en,v);    if (!res && mid
         
          mx+1==y->mn) return 1; if (x->mn-1==y->mx) return -1; return 0;}void insert(Node *x){ int tmp; if (top && st[top]->xihe==1 && (tmp=ok(st[top]->lst,x))){ if (tmp==1) st[top]->mx=x->mx; else st[top]->mn=x->mn; st[top]->lst=x; st[top]->r=x->r; x->fa=st[top--]; insert(x->fa); return; } if (top && (tmp=ok(st[top],x))){ if (tmp==1) d[++cnt]={null,x,st[top]->mn,x->mx,1,st[top]->l,x->r}; else d[++cnt]={null,x,x->mn,st[top]->mx,1,st[top]->l,x->r}; st[top--]->fa=x->fa=&d[cnt]; insert(x->fa); return; } for (int i=top,mn=x->mn,mx=x->mx;i && L[x->r]<=st[i]->r;--i){ mn=min(mn,st[i]->mn); mx=max(mx,st[i]->mx); if (mx-mn+1==x->r-st[i]->l+1){ d[++cnt]={null,x,mn,mx,0,st[i]->l,x->r}; x->fa=&d[cnt]; for (;top>=i;--top) st[top]->fa=&d[cnt]; insert(x->fa); return; } } st[++top]=x;}int f[N*2][18],dep[N*2];void getdep(int x){ if (dep[x] || x==0) return; getdep(f[x][0]); dep[x]=dep[f[x][0]]+1;}inline void getans(int u,int v){ if (dep[u]>dep[v]){ for (int k=dep[u]-dep[v],i=0;k;k>>=1,++i) if (k&1) u=f[u][i]; } else for (int k=dep[v]-dep[u],i=0;k;k>>=1,++i) if (k&1) v=f[v][i]; for (int i=17;i>=0;--i) if (f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i]; if (d[f[u][0]].xihe==0) printf("%d %d\n",d[f[u][0]].l,d[f[v][0]].r); else printf("%d %d\n",d[u].l,d[v].r);}int main(){ freopen("c.in","r",stdin); freopen("c.out","w",stdout); scanf("%d",&n); for (int i=1;i<=n;++i) scanf("%d",&a[i]); for (int i=1;i<=n;++i){ for (;tn && a[smn[tn]]>a[i];--tn) add(1,1,n,smn[tn-1]+1,smn[tn],a[smn[tn]]-a[i]); for (;tx && a[smx[tx]]
          
           l==1 && st[top]->r==n); for (int i=1;i<=cnt;++i) f[i][0]=d[i].fa-d; for (int i=1;i<=cnt;++i) getdep(i); for (int i=1;i<=17;++i) for (int j=1;j<=cnt;++j) f[j][i]=f[f[j][i-1]][i-1]; int Q; scanf("%d",&Q); while (Q--){ int l,r; scanf("%d%d",&l,&r); getans(num[l],num[r]); } return 0;}
          
         
        
       
      
     
    

---

到此为止了么？

不，实际上有真正的\(O(n)\)解法。

对于一个区间\([l,r]\)，找到\([l,r]\)中的最大值\(mx\)和最小值\(mn\)。

然后找到值为\([mn,mx]\)的最右位置\(R\)。显然，如果\(r<R\)，那么以\(r\)为右端点的最大区间左端点小于\(l\)。也就是说，不存在\(L<l\)的区间\([L,r]\)包含\([l,r]\)。

在做第三个操作的时候，沿路记下\(mn\)和\(mx\)，求出\(R\)。如果\(r<R\)，就不用做下去了，因为\(R\)只会越来越大。

求的时候直接用\(RMQ\)，\(O(1)\)处理询问。

这是个非常好的优化，尽管它看起来仍然是\(O(n^2)\)的，但是数据似乎不怎么卡。

为了满足强迫症的想法，我们使劲将它优化到\(O(n)\)。

对于栈中的每个点，可以记录一个\(fail\)指针表示它之前找到的第一个\(r<R\)的地方。

那么以后就不需要暴力找，只需要跳\(fail\)来找。

每条\(fail\)边只会跳\(O(1)\)次（跳了意味着这次\(R\leq r\)，如果在后来还没有成功，\(fail_r\)一定会指向一个更前的点。这样在后来跳的时候，再也不会经过这条边。）

所以这样做的时间复杂度是\(O(n)\)的！

然而，我们愕然发现预处理的时间复杂度依然是\(O(n\lg n)\)……

先放个代码：

using namespace std;#include 
    
     #include 
     
      #include 
      
       #include 
       
        //#include 
        
         #define N 100010int lg[N];int n,a[N];int mx[N][17];inline int query(int l,int r){    int m=lg[r-l+1];    return max(mx[l][m],mx[r-(1<
         
          mx+1==y->mn?1:(x->mn-1==y->mx?-1:0);}void insert(Node *x){ if (!top){ st[++top]=x; fail[top]=0; mnf[top]=x->mn; mxf[top]=x->mx; return; } int tmp; if (st[top]->xihe==1 && (tmp=ok(st[top]->lst,x))){ if (tmp==1) st[top]->mx=x->mx; else st[top]->mn=x->mn; st[top]->lst=x; st[top]->r=x->r; x->fa=st[top]; top--; insert(x->fa); return; } if (tmp=ok(st[top],x)){ if (tmp==1) d[++cnt]={null,x,st[top]->mn,x->mx,1,st[top]->l,x->r}; else d[++cnt]={null,x,x->mn,st[top]->mx,1,st[top]->l,x->r}; st[top]->fa=x->fa=&d[cnt]; top--; insert(x->fa); return; } for (int i=top,mn=x->mn,mx=x->mx;i;mn=min(mn,mnf[i]),mx=max(mx,mxf[i]),i=fail[i]){ mn=min(mn,st[i]->mn); mx=max(mx,st[i]->mx); if (query(mn,mx)>x->r){ st[++top]=x; fail[top]=i; mnf[top]=mn; mxf[top]=mx; return; } if (mx-mn+1==x->r-st[i]->l+1){ d[++cnt]={null,x,mn,mx,0,st[i]->l,x->r}; x->fa=&d[cnt]; for (;top>=i;--top) st[top]->fa=&d[cnt]; insert(x->fa); return; } }}int f[N*2][18],dep[N*2];void getdep(int x){ if (dep[x] || x==0) return; getdep(f[x][0]); dep[x]=dep[f[x][0]]+1;}inline void getans(int u,int v){ if (dep[u]>dep[v]){ for (int k=dep[u]-dep[v],i=0;k;k>>=1,++i) if (k&1) u=f[u][i]; } else for (int k=dep[v]-dep[u],i=0;k;k>>=1,++i) if (k&1) v=f[v][i]; for (int i=17;i>=0;--i) if (f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i]; if (d[f[u][0]].xihe==0) printf("%d %d\n",d[f[u][0]].l,d[f[v][0]].r); else printf("%d %d\n",d[u].l,d[v].r);}int main(){ freopen("c.in","r",stdin); freopen("c.out","w",stdout); scanf("%d",&n); lg[0]=0,lg[1]=0; for (int i=2;i<=n;++i) lg[i]=lg[i>>1]+1; for (int i=1;i<=n;++i) scanf("%d",&a[i]); for (int i=1;i<=n;++i) mx[a[i]][0]=i; for (int i=1;1<
          <=n;++i) for (int j=1;j+(1<
           
            <=n;++j) mx[j][i]=max(mx[j][i-1],mx[j+(1<
           
         
        
       
      
     
    

---

接着我们考虑如何处理\([l,r]\)的询问。

其实只要处理出所有\(i \in [l,r)\)的\([i,i+1]\)的并，就是\([l,r]\)询问的答案。

对于栈中的每个节点，处理出\([l,r]\)的答案（好像是\([l,r)\)？）。对于每条\(fail\)边，处理出中间答案的并。

所以现在的问题是求所有\([i,i+1]\)的答案。

实际上这可以看成许多个区间询问，然而我们要\(O(n)\)来预处理出这些东西。

区间询问怎么预处理？有个很牛的方法是\(O(n)\)建出笛卡尔树，然后变成\(LCA\)问题。用\(Tarjan-LCA\)来求。这样就可以达到\(O(n)\)了。

或者也可以在建树之后用\(+1-1RMQ\)来解决，然而我没有打过。

所以实际上\(O(n)\)好像没有什么用啊……毕竟如果出题，肯定不只是析合树，然而其它操作总是要\(\lg\)级别的……

而且这样代码复杂度还很恐怖……

我没打过，别找我拿标程……

---

如果真的要打析合树，用线段树的\(O(n\lg n)\)方法似乎是一种不错的选择，因为思路比较简单。

或者用\(O(n\lg n)\)预处理\(ST\)表来搞，还有记录\(fail\)边，这样代码长度会短一些。

至于纯正的\(O(n)\)……就在嘴巴上说说算了吧……