BZOJ3282Tree——LCT-白红宇

BZOJ3282Tree——LCT

阅读量：5783 次

发布时间：2019-06-18

本文共 2403 字，大约阅读时间需要 8 分钟。

题目描述

给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。

操作有４种。操作从０到３编号。点从１到Ｎ编号。

０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。

保证ｘ到ｙ是联通的。

１：后接两个整数（ｘ，ｙ），代表连接ｘ到ｙ，若ｘ到Ｙ已经联通则无需连接。

２：后接两个整数（ｘ，ｙ），代表删除边（ｘ，ｙ），不保证边（ｘ，ｙ）存在。

３：后接两个整数（ｘ，ｙ），代表将点Ｘ上的权值变成Ｙ。

输入

第１行两个整数,分别为Ｎ和Ｍ,代表点数和操作数。

第２行到第Ｎ＋１行,每行一个整数,整数在［１,１０＾９］内,代表每个点的权值。

第Ｎ＋２行到第Ｎ＋Ｍ＋１行,每行三个整数,分别代表操作类型和操作所需的量。

１＜＝Ｎ，Ｍ＜＝３０００００

输出

对于每一个０号操作，你须输出Ｘ到Ｙ的路径上点权的Ｘｏｒ和。

样例输入

3 3

1 1 2

0 1 2

0 1 1

样例输出

LCT模板题，splay维护子树异或和即可。因为cut时不保证边存在，所以注意cut时的判断。

#include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 using namespace std;int n,m;int x,y;int opt;int v[300010];int f[300010];int s[300010][2];int st[300010];int r[300010];int sum[300010];int get(int rt){ return rt==s[f[rt]][1];}void pushup(int rt){ sum[rt]=v[rt]^sum[s[rt][0]]^sum[s[rt][1]];}void pushdown(int rt){ if(r[rt]) { swap(s[rt][0],s[rt][1]); r[s[rt][0]]^=1; r[s[rt][1]]^=1; r[rt]^=1; }}int is_root(int rt){ return s[f[rt]][0]!=rt&&s[f[rt]][1]!=rt;}void rotate(int rt){ int fa=f[rt]; int anc=f[fa]; int k=get(rt); if(!is_root(fa)) { s[anc][fa==s[anc][1]]=rt; } s[fa][k]=s[rt][k^1]; f[s[fa][k]]=fa; s[rt][k^1]=fa; f[fa]=rt; f[rt]=anc; pushup(fa); pushup(rt);}void splay(int rt){ int top=0; st[++top]=rt; for(int i=rt;!is_root(i);i=f[i]) { st[++top]=f[i]; } for(int i=top;i>=1;i--) { pushdown(st[i]); } for(int fa;!is_root(rt);rotate(rt)) { if(!is_root(fa=f[rt])) { rotate(get(rt)==get(fa)?fa:rt); } }}void access(int rt){ for(int x=0;rt;x=rt,rt=f[rt]) { splay(rt); s[rt][1]=x; pushup(rt); }}void reverse(int rt){ access(rt); splay(rt); r[rt]^=1;}int find(int rt){ access(rt); splay(rt); while(s[rt][0]) { rt=s[rt][0]; } return rt;}void link(int x,int y){ reverse(x); f[x]=y;}void cut(int x,int y){ reverse(x); access(y); splay(y); if(s[x][1]||f[x]!=y||s[y][get(x)^1]) { return ; } s[y][0]=f[x]=0;}void change(int rt,int x){ v[rt]=x; access(rt); splay(rt);}int query(int x,int y){ reverse(x); access(y); splay(y); return sum[y];}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&v[i]); } while(m--) { scanf("%d%d%d",&opt,&x,&y); if(opt==0) { printf("%d\n",query(x,y)); } else if(opt==1&&find(x)!=find(y)) { link(x,y); } else if(opt==2&&find(x)==find(y)) { cut(x,y); } else if(opt==3) { change(x,y); } }}