【学习笔记】析合树
定義
為了方便，下面的定義都是對一個\(n\)階排列
定義一個段的值域$ran[l,r] = [min ?a_i ?, ?max ?a_i] (l \le i \le r) $ ，對于一個排列\(ran[l,r] \ge r-l+1\)
定義1 一個段是連續的，當且\(|ran[l,r]|= r-l+1\) ，顯然$ \varnothing ,[1,n],[i,i]$都是連續的
性質1：
對于兩個連續段，它們的交一定是一個連續段
對于兩個有交的連續段，它們的并一定是一個連續段
對于有交的\(A,B\)，就只需要考慮 $ A\cap B , A \cup B $了，所以這意味著啥？
定義2 一個連續段是本原連續段，當且僅當滿足不存在和它相交卻沒有包含關系的連續段
這樣的連續段可以看成一個節點個數\(O(n)\)的樹
定義3 定義上面由本原連續段形成的樹為排列的析合樹
性質2 :
? 析合樹的節點的兒子一定滿足下列性質之一：
將兒子節點連續段看成一個整體，形成了兒子序列，選一段是兒子區間
? 1.不存在任何一個兒子節點非平凡區間組成連續段，稱為析點
? 2.任何兒子節點組成的區間都是連續段，稱為合點
證明：
對于一個非平凡(不是所有或單個的兒子區間)是連續段，它不是本原的，那么一定存在另外一個連續段和它相交，注意到性質1中相交之后的三個部分是相對有序的，再考慮它們的并，這樣下去一定可以得到完全覆蓋整個兒子區間的很多個區間，它們是相對有序的，如果這些小區間不是平凡的，再進行這樣的操作，最后得到兒子區間都是相對有序的，所以是滿足非析即和性質的性質3 :
? 析合樹可以構成所有連續段，且所有連續段在析合樹上一定是以下兩種形式：
? 1.樹節點構成的連續段
? 2.合點的非平凡兒子區間構成的連續段
證明：
根據性質1，所有不可拆分的連續段一定都在樹節點上，考慮一個連續段由\(v_1,v_2,\cdots,v_k(k>1)\)構成且，那找\(v_1\)到\(v_k\)的lca，由于v1到vk是連續拼接的并且lca的親生兒子全部是本原的，所以一定可以用lca的直接兒子去代替這個區間
構造
基本方法：
考慮增量，假設做到i，已經得到了\(1->i-1\)位的析合森林，用一個棧維護這個析合森林
用下面的方法進行增量：
設置一個當前點\(now\)，初始為\([i,i]\)，考慮棧頂的點為top
1.如果top是合點，并且now可以作為它的最后一個兒子，那么將now設置為top的最后一個兒子，彈出top為新的now，重復這個過程
2.否則從top開始往回找到最少的棧頂的若干個點可以和now組成連續段，彈出他們，新加一個點向這些點和原來的now連邊，將now設置為新點，重復這個過程
直到棧為空或2找不到
說明：//這里仔細想想好像有點不大嚴謹所以改成說明了。。。
? 已經出棧的點無論如何增量一定是本原的，首先它現在一定是本原的
? 把和以后它相交的連續段與它的父親取個交一定可以得到現在就和它相交的段，即它現在就不本原了
? 新加入連續段，需要考慮的本原連續段一定是和棧頂的一部分森林形成的
? 嘗試歸納now一定是\([1,i]\)的本原連續段，顯然\([i,i]\)是的，設下次的now為now'
? 如果now‘不本原一定存在什么和它相交，考慮它的r可能在哪里
? 由于now是本原所以，這個連續段的r一定不會在now
? 這樣一定是增量之前已經存在的連續段顯然和now'不會相交
復雜度分析：
1是\(O(n)\)的，如果在2中被合并掉的點是\(O(n)\)的，但是如果到最后都無法合并，復雜度可能會退化到\(O(n^2)\)，所以需要一個\(L_i\)表示以\(i\)為右端點的連續段的最遠左端點，超過了就break就\(O(n)\)了如何求\(L\) :
線段樹對r動態維護\(max(l,r)-min(l,r)-(r-l)\)取最小值0最前面的l即可
max和min可以利用單調棧維護
LCA ppt里的O(n)做法感覺除了建樹以外用處不是很大，所以沒有寫
例題
n階排列，詢問包含\([l_i,r_i]\)的最小連續段
建出析合樹之后根據性質 3 找到lca，如果它是析點那么答案就是它的區間，否則是l,r方向的直接兒子形成的兒子區間
code
#include<bits/stdc++.h> #define il inline #define rg register using namespace std; const int N=200010; int n,m,a[N],st1[N],st2[N],tp1,tp2,rt,L[N],R[N],M[N],id[N],cnt,typ[N],bin[20],st[N],tp;il int min(int x,int y){if(x<y)return x;return y;} il int max(int x,int y){if(x>y)return x;return y;} char gc(){static char*p1,*p2,s[1000000];if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);return(p1==p2)?EOF:*p1++; } int rd(){int x=0;char c=gc();while(c<'0'||c>'9')c=gc();while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc();return x; } char ps[1000000],*pp=ps; void flush(){fwrite(ps,1,pp-ps,stdout);pp=ps;} void push(char x){if(pp==ps+1000000)flush();*pp++=x;} void write(int l,int r){static int sta[N],top;if(!l)push('0');else{while(l)sta[++top]=l%10,l/=10;while(top)push(sta[top--]^'0');}push(' ');if(!r)push('0');else{while(r)sta[++top]=r%10,r/=10;while(top)push(sta[top--]^'0');}push('\n'); }struct RMQ{int lg[N],mn[N][17],mx[N][17];void chkmn(int&x,int y){if(x>y)x=y;}void chkmx(int&x,int y){if(x<y)x=y;}void build(){for(int i=bin[0]=1;i<20;++i)bin[i]=bin[i-1]<<1;for(int i=2;i<=n;++i)lg[i]=lg[i>>1]+1;for(int i=1;i<=n;++i)mn[i][0]=mx[i][0]=a[i];for(int i=1;i<17;++i)for(int j=1;j+bin[i]-1<=n;++j)mn[j][i]=min(mn[j][i-1],mn[j+bin[i-1]][i-1]),mx[j][i]=max(mx[j][i-1],mx[j+bin[i-1]][i-1]);}int ask_mn(int l,int r){int t=lg[r-l+1];return min(mn[l][t],mn[r-bin[t]+1][t]);}int ask_mx(int l,int r){int t=lg[r-l+1];return max(mx[l][t],mx[r-bin[t]+1][t]);} }D; //維護L_i struct SEG{#define ls (k<<1)#define rs (k<<1|1)int mn[N<<1],ly[N<<1];void pushup(int k){mn[k]=min(mn[ls],mn[rs]);}void mfy(int k,int v){mn[k]+=v,ly[k]+=v;}void pushdown(int k){if(ly[k])mfy(ls,ly[k]),mfy(rs,ly[k]),ly[k]=0;}void update(int k,int l,int r,int x,int y,int v){if(l==x&&r==y){mfy(k,v);return;}pushdown(k);int mid=(l+r)>>1;if(y<=mid)update(ls,l,mid,x,y,v);else if(x>mid)update(rs,mid+1,r,x,y,v);else update(ls,l,mid,x,mid,v),update(rs,mid+1,r,mid+1,y,v);pushup(k);}int query(int k,int l,int r){if(l==r)return l;pushdown(k);int mid=(l+r)>>1;if(!mn[ls])return query(ls,l,mid);else return query(rs,mid+1,r);} }T;int o=1,hd[N],dep[N],fa[N][18]; struct Edge{int v,nt;}E[N<<1]; void add(int u,int v){E[o]=(Edge){v,hd[u]};hd[u]=o++; // printf("%d %d\n",u,v); } void dfs(int u){for(int i=1;bin[i]<=dep[u];++i)fa[u][i]=fa[fa[u][i-1]][i-1];for(int i=hd[u];i;i=E[i].nt){int v=E[i].v;dep[v]=dep[u]+1;fa[v][0]=u;dfs(v);} } int go(int u,int d){for(int i=0;i<18&&d;++i)if(bin[i]&d)d^=bin[i],u=fa[u][i];return u;} int lca(int u,int v){if(dep[u]<dep[v])swap(u,v);u=go(u,dep[u]-dep[v]);if(u==v)return u;for(int i=17;~i;--i)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];return fa[u][0]; } bool judge(int l,int r){return D.ask_mx(l,r)-D.ask_mn(l,r)==r-l;} //建樹 void build(){for(int i=1;i<=n;++i){//單調棧while(tp1&&a[i]<=a[st1[tp1]])T.update(1,1,n,st1[tp1-1]+1,st1[tp1],a[st1[tp1]]),tp1--;while(tp2&&a[i]>=a[st2[tp2]])T.update(1,1,n,st2[tp2-1]+1,st2[tp2],-a[st2[tp2]]),tp2--;T.update(1,1,n,st1[tp1]+1,i,-a[i]);st1[++tp1]=i;T.update(1,1,n,st2[tp2]+1,i,a[i]);st2[++tp2]=i;id[i]=++cnt;L[cnt]=R[cnt]=i;int le=T.query(1,1,n),now=cnt;while(tp&&L[st[tp]]>=le){if(typ[st[tp]]&&judge(M[st[tp]],i)){R[st[tp]]=i;add(st[tp],now);now=st[tp--];}else if(judge(L[st[tp]],i)){typ[++cnt]=1;//合點一定是被這樣建出來的L[cnt]=L[st[tp]];R[cnt]=i;M[cnt]=L[now];add(cnt,st[tp--]);add(cnt,now);now=cnt;}else{add(++cnt,now);do add(cnt,st[tp--]);while(tp&&!judge(L[st[tp]],i));L[cnt]=L[st[tp]];R[cnt]=i;add(cnt,st[tp--]);now=cnt;}}st[++tp]=now;T.update(1,1,n,1,i,-1);}rt=st[1]; } void query(int r,int l){int x=id[l],y=id[r];int z=lca(x,y);if(typ[z]&1)l=L[go(x,dep[x]-dep[z]-1)],r=R[go(y,dep[y]-dep[z]-1)];else l=L[z],r=R[z];write(l,r); }//分lca為析或和，這里把葉子看成析的int main(){freopen("c.in","r",stdin);freopen("c.out","w",stdout);n=rd();for(int i=1;i<=n;++i)a[i]=rd();D.build();build();dfs(rt);m=rd();for(int i=1;i<=m;++i)query(rd(),rd());return flush(),0; } //20190612 //析合樹
轉載于:https://www.cnblogs.com/Paul-Guderian/p/11020708.html
總結
- 上一篇： Python虚拟环境virtualenv
- 下一篇： Guava Cache用法介绍