明明是裸 LCT 板子......
注意 pshp 的那个地方! 原以为把 0~n 的 mx,mn 都赋好初值就能随便弄了, 仔细想想要用的是 val!
而且还是既用在 max 里又用在 min 里, 故不能赋初值来怎样, 应当分类讨论!
关于变成相反数的操作, 原来也是打标记! 而且标记的含义和线段树的一样, 表示自己已经操作过, 要给孩子操作. 这样才能保证 query 的正确.
可是自己那种 dfs 来当即弄成相反数的做法为什么不行???
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- using namespace std;
- const int N=2e4+5,M=4e4+5;
- int n,m,pre[M],sum[M],val[M],mx[M],mn[M],c[M][2],stack[M],top,sta[M];
- bool rev[M];
- bool isroot(int x){return c[pre[x]][0]!=x&&c[pre[x]][1]!=x;}
- void pshp(int x)
- {
- int ls=c[x][0],rs=c[x][1];
- sum[x]=val[x]+sum[ls]+sum[rs];
- mx[x]=max(mx[ls],mx[rs]);
- mn[x]=min(mn[ls],mn[rs]);
- if(x>n)mx[x]=max(val[x],mx[x]),mn[x]=min(val[x],mn[x]);
- // mx[x]=max(val[x],max(mx[ls],mx[rs]));
- // mn[x]=min(val[x],min(mn[ls],mn[rs]));
- }
- void reverse(int x)
- {
- if(rev[x])
- {
- rev[c[x][0]]^=1;rev[c[x][1]]^=1;
- swap(c[x][0],c[x][1]);
- rev[x]=0;
- }
- }
- void rotate(int x)
- {
- int y=pre[x],z=pre[y],d=(x==c[y][1]);
- if(!isroot(y))c[z][y==c[z][1]]=x;
- pre[x]=z;pre[y]=x;
- c[y][d]=c[x][!d];pre[c[x][!d]]=y;c[x][!d]=y;
- pshp(y);pshp(x);
- }
- void splay(int x)
- {
- stack[top=1]=x;
- for(int t=x;!isroot(t);t=pre[t])stack[++top]=pre[t];
- for(;top;top--)reverse(stack[top]);
- for(;!isroot(x);rotate(x))
- {
- int y=pre[x],z=pre[y];
- if(isroot(y))continue;
- ((x==c[y][0])^(y==c[z][0]))?rotate(x):rotate(y);
- }
- }
- void access(int x)
- {
- for(int t=0;x;c[x][1]=t,pshp(x),t=x,x=pre[x])splay(x);
- }
- void makeroot(int x)
- {
- access(x);splay(x);rev[x]^=1;
- }
- void query(int x,int y)
- {
- makeroot(x);access(y);splay(y);
- }
- void link(int x,int y)
- {
- makeroot(x);pre[x]=y;
- }
- void dfs(int cr)
- {
- val[cr]=-val[cr];
- if(c[cr][0])dfs(c[cr][0]);
- if(c[cr][1])dfs(c[cr][1]);
- pshp(cr);
- }
- int main()
- {
- scanf("%d",&n);int x,y,z;
- mx[0]=-1005;mn[0]=1005;// 写在 link 前
- for(int i=1;i<n;i++)
- {
- scanf("%d%d%d",&x,&y,&z);x++;y++;
- val[i+n]=z;
- link(i+n,x);link(i+n,y);
- }
- char ch[5];
- scanf("%d",&m);
- while(m--)
- {
- scanf("%s%d%d",ch,&x,&y);
- if(ch[0]!='C')x++,y++,query(x,y);// 仅!='C'时 ++!!!
- if(ch[0]=='C'){
- splay(x+n);val[x+n]=y;pshp(x+n);
- }
- else if(ch[0]=='N')dfs(x);
- else if(ch[1]=='U')printf("%d\n",sum[y]);
- else if(ch[1]=='A')printf("%d\n",mx[y]);
- else printf("%d\n",mn[y]);
- }
- return 0;
- }
会 WA 的做法
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- using namespace std;
- const int N=2e4+5,M=4e4+5;
- int n,m,pre[M],sum[M],val[M],mx[M],mn[M],c[M][2],stack[M],top,sta[M],tp;
- bool rev[M],tag[M];
- bool isroot(int x){return c[pre[x]][0]!=x&&c[pre[x]][1]!=x;}
- void pshp(int x)
- {
- int ls=c[x][0],rs=c[x][1];
- sum[x]=val[x]+sum[ls]+sum[rs];
- mx[x]=max(mx[ls],mx[rs]);
- mn[x]=min(mn[ls],mn[rs]);
- if(x>n)mx[x]=max(mx[x],val[x]),mn[x]=min(mn[x],val[x]);//////
- // mx[x]=max(val[x],max(mx[ls],mx[rs]));
- // mn[x]=min(val[x],min(mn[ls],mn[rs]));
- }
- void tg(int x)
- {
- sum[x]=-sum[x];val[x]=-val[x];tag[x]^=1;
- swap(mn[x],mx[x]);mx[x]=-mx[x];mn[x]=-mn[x];
- }
- void pshd(int x)
- {
- int ls=c[x][0],rs=c[x][1];
- if(rev[x])
- {
- rev[ls]^=1;rev[rs]^=1;
- swap(c[x][0],c[x][1]);
- rev[x]=0;
- }
- if(tag[x])
- {
- tag[x]=0;if(ls)tg(ls);if(rs)tg(rs);
- }
- }
- void rotate(int x)
- {
- int y=pre[x],z=pre[y],d=(x==c[y][1]);
- if(!isroot(y))c[z][y==c[z][1]]=x;
- pre[x]=z;pre[y]=x;
- c[y][d]=c[x][!d];pre[c[x][!d]]=y;c[x][!d]=y;
- pshp(y);pshp(x);
- }
- void splay(int x)
- {
- stack[top=1]=x;
- for(int t=x;!isroot(t);t=pre[t])stack[++top]=pre[t];
- for(;top;top--)pshd(stack[top]); // 倒序, 标记才能全清除
- for(;!isroot(x);rotate(x))
- {
- int y=pre[x],z=pre[y];
- if(isroot(y))continue;
- ((x==c[y][0])^(y==c[z][0]))?rotate(x):rotate(y);
- }
- }
- void access(int x)
- {
- for(int t=0;x;splay(x),c[x][1]=t,pshp(x),t=x,x=pre[x]);
- }
- void makeroot(int x)
- {
- access(x);splay(x);rev[x]^=1;
- }
- void query(int x,int y)
- {
- makeroot(x);access(y);splay(y);
- }
- void link(int x,int y)
- {
- makeroot(x);pre[x]=y;
- }
- void chg(int x,int y)
- {
- splay(x);val[x]=y;pshp(x);//splay 即可, 不用 makeroot
- }
- int main()
- {
- scanf("%d",&n);int x,y,z;
- mx[0]=-1005;mn[0]=1005;
- // for(int i=0;i<=n;i++)mx[i]=-1005,mn[i]=1005;//
- for(int i=1;i<n;i++)
- {
- scanf("%d%d%d",&x,&y,&z);x++;y++;
- val[i+n]=z;
- link(i+n,x);link(i+n,y);
- }
- char ch[5];
- scanf("%d",&m);
- while(m--)
- {
- scanf("%s%d%d",ch,&x,&y);
- if(ch[0]!='C')x++,y++,query(x,y);// 仅!='C'时 ++!!!
- if(ch[0]=='C')chg(x+n,y);
- else if(ch[0]=='N')tg(y);
- else if(ch[1]=='U')printf("%d\n",sum[y]);
- else if(ch[1]=='A')printf("%d\n",mx[y]);
- else printf("%d\n",mn[y]);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2663553.html