Luogu4332

LOJ2187

題解

代碼-Tea

題意 : 每個點有三個兒子 , 給定葉節點的權值\(0\)或\(1\)且支持修改 , 非葉子節點的權值為當有\(>=2\)個兒子的權值為\(1\)的時候取\(1\) , 每次修改后求根節點輸出
定義 : 權值可以取\(0,1,2,3\) ; 輸出為\(0\)或\(1\)且權值\(>=2\)時輸出為\(1\) .
限制 : 修改的都是葉子節點

考慮如果把輸出\(0\)改成\(1\) , 則找到祖先中最深的權值不為\(1\)的點 , 這條鏈上的輸出會改變 , 這里用\(LCT\)維護
如果把輸出\(1\)改成\(0\) , 則找到祖先中最深的權值不為 \(2\) 的點 , 這條鏈上的輸出會改變為\(0\)

這樣有點麻煩 , 來一個轉化 , 葉節點權值取值范圍由\(0,1\)變為\(1,2\) ; 統一變成了權值\(2\)會對父親產生貢獻 , 權值\(1\)對父親沒有貢獻

定義\(not1[x]=true\)的意義是\(x\)的子樹中存在 權值不為\(1\)的點 , \(not2[]\)類似 .
只要寫了\(pushdown\) , \(LCT\)也能區間打標記 .

打標記時先潦草地搞一下有類似\(not2[x]=not1[x],not1[x]=0\)的操作 , 之后在\(pushup\)的時候會有簡單而正確的更新 : \(not1[x]=not1[ls]\ |\ not1[rs]\ |\ (val[x]!=1);\)
一定要想清楚所有狀況才能說明這是對的 : 如果把\(0\)改成\(1\) , 可能碰到一個權值為\(0\)的點變成\(1\) , 或者\(2\)變成\(3\)而停止 ;
如果把\(1\)變成\(0\) , 可能碰到一個權值為\(1\)的點變成\(0\) , 或者\(3\)變成\(2\)而停止 .

所以\(pushup\)是\(LCT\)的關鍵 , 也是所有數據結構的關鍵 , 盡管在一般線段樹題目中看不出來 ,
但在復雜一點的比如P4198樓房重建和 [HNOI/AHOI2018]轉盤便顯得非常重要了 .
類似地 , [NOIP2018]保衛王國中從下往上轉移使得矩陣乘的更新順序改變 , 說明\(pushup\)操作真的非常重要.
最簡單的操作卻能更新很難更新的情況,從而維護正確性

這道題還用到了一個點 , \(access\)可以使無關的點斷開 , 而不直接\(fa[x]=0,ch[y][_]=0\)是因為\(access\)包括了\(pushup\)的更新
兩個端點找出來以后就可以用上面說的修改和打標記了

注釋更新于\(19.3.29\)

#include<bits/stdc++.h> #define debug(...) fprintf(stderr,__VA_ARGS__) #define Debug(x) cout<<#x<<"="<<x<<endl using namespace std; typedef long long LL; const int INF=1e9+7; inline LL read(){register LL x=0,f=1;register char c=getchar();while(c<48||c>57){if(c=='-')f=-1;c=getchar();}while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();return f*x; }const int MAXN=1.5e6+5;int fa[MAXN],to[MAXN][3]; int n,m;namespace LCT{int par[MAXN],ch[MAXN][2],val[MAXN],tag[MAXN];bool not1[MAXN],not2[MAXN];//定義not1[x]=true的意義是x的子樹中存在權值不為1的點int st[MAXN],top; #define ls (ch[rt][0]) #define rs (ch[rt][1])inline bool chk(int x){return ch[par[x]][1]==x;}inline bool isnotroot(int x){return ch[par[x]][0]==x||ch[par[x]][1]==x;}inline void pushup(int rt){not1[rt]=not1[ls]|not1[rs]|(val[rt]!=1);//最簡單的維護卻可以更新很難更新的情況,從而維護正確性. pushup是LCT的關鍵not2[rt]=not2[ls]|not2[rs]|(val[rt]!=2);}inline void modify(int x,int y){val[x]+=y,tag[x]+=y;//區間樹上打標記if(y>0) not2[x]=not1[x],not1[x]=0;//對整段val[]=1的區間加1,val[i]=0變1的誤判會在pushup()里改正,然后就沒有別的情況了else not1[x]=not2[x],not2[x]=0;//這里的修改只是簡單的維護}inline void pushdown(int rt){if(!tag[rt]) return;if(ls) modify(ls,tag[rt]);if(rs) modify(rs,tag[rt]);tag[rt]=0;}inline void rotate(int x){int y=par[x],z=par[y],k=chk(x),w=ch[x][k^1];ch[y][k]=w,par[w]=y;if(isnotroot(y)) ch[z][chk(y)]=x; par[x]=z;ch[x][k^1]=y,par[y]=x;pushup(y);pushup(x);}inline void splay(int x){int y=x,top=0;while(1){st[++top]=y;if(isnotroot(y)) y=par[y];else break;}while(top) pushdown(st[top--]);while(isnotroot(x)){int y=par[x];if(isnotroot(y)){if(chk(x)==chk(y)) rotate(y);else rotate(x);}rotate(x);}}inline void access(int x){for(int y=0;x;x=par[y=x])splay(x),ch[x][1]=y,pushup(x);}inline int findnot1(int rt){pushdown(rt);if(!not1[rt]) return 0;if(not1[rs]) return findnot1(rs);//找到深度最大的不是1的點,即能夠影響到的最遠的點if(val[rt]!=1) return rt;return findnot1(ls);}inline int findnot2(int rt){pushdown(rt);if(!not2[rt]) return 0;if(not2[rs]) return findnot2(rs);if(val[rt]!=2) return rt;return findnot2(ls);} #undef ls #undef rs }using namespace LCT;inline void dfs(int u){if(u>n) return;//因為初始數據一定是合法的,所以沒必要往更深的地方走for(int i=0;i<=2;i++){int v=to[u][i];dfs(v);val[u]+=(val[v]>>1);//只有權值>=1的才有意義,先簡單搞一下貢獻} // val[u]>>=1; }int main(){ // freopen("asd.in","r",stdin);n=read();for(int i=1;i<=n;i++)for(int j=0;j<=2;j++){int x=read();to[i][j]=x;par[x]=i,fa[x]=i;}for(int i=n+1;i<=3*n+1;i++) val[i]=read()+1;//根據定義,val[u]應該+=(val[v]/2).(對于底層節點(其實適應于所有節點))考慮到轉換的方便用1和2表示.//1就代表對上一層沒貢獻,2就代表有貢獻.dfs(1);//算出初始的答案m=read();for(int i=1;i<=m;i++){int x=read();//實際上這里是一種卡常,如果split(x,y)就要makeroot極慢,所以改為這樣access(x);splay(x);if(val[x]>1){int y=findnot2(ch[x][0]); // Debug(fa[y]); fa[y]是原樹中的父親,不是splay中的.access(fa[y]);//這里的作用是把無關的點斷開,要access的理由是包括了pushup操作.splay(x);//access中使得根變了,所以要重新splay.modify(x,-1);}else{int y=findnot1(ch[x][0]);access(fa[y]);splay(x);modify(x,1);}splay(1);//要把1節點旋上來才能更新答案printf("%d\n",val[1]>>1);} }

3.2原始注釋

轉載于:https://www.cnblogs.com/lizehon/p/10462097.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的P4332 [SHOI2014]三叉神经树(LCT)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。