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原始注释

05-11 13:45