[bzoj3282]Tree

Description

给定\(N\)个点以及每个点的权值,要你处理接下来的\(M\)个操作.操作有\(4\)种.操作从\(0\)到\(3\)编号.点从\(1\)到\(N\)编号.
\(0\):后接两个整数\((x,y)\),代表询问从\(x\)到\(y\)的路径上的点的权值的\(xor\)和.保证\(x\)到\(y\)是联通的.
\(1\):后接两个整数\((x,y)\),代表连接\(x\)到\(y\),若\(x\)到\(y\)已经联通则无需连接.
\(2\):后接两个整数\((x,y)\),代表删除边\((x,y)\),不保证边\((x,y)\)存在.
\(3\):后接两个整数\((x,y)\),代表将点\(x\)上的权值变成\(y\).

Input

第\(1\)行\(2\)个整数\(N,M\),代表点数和操作数.
第\(2\)行到第\(N+1\)行,每行\(1\)个整数,整数\(\in[1,10^9]\),代表每个点的权值.
第\(N+2\)行到第\(N+M+1\)行,每行\(3\)个整数,分别代表操作类型和操作所需的量.

Output

对于每一个\(0\)号操作,你须输出\(x\)到\(y\)的路径上点权的\(xor\)和.

Sample Input

3 3 
1
2
3
1 1 2
0 1 2 
0 1 1

Sample Output

3
1

HINT

\(1\leq{N,M}\leq300000\).

Solution

\(LCT\)裸题,\(Splay\)维护\(xor\)和.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 300010
using namespace std;
typedef long long ll;
struct Splay{
    int c[2],f,sum,rev;//树边方向
}tr[N];//大小看深度,维护实路径,最左/右端点对应路径头/尾 
int w[N],n,m;
stack s;
inline int read(){
    int ret=0;char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        ret=(ret<<1)+(ret<<3)+c-'0';
        c=getchar();
    }
    return ret;
}
inline bool son(int u){
    return tr[tr[u].f].c[1]==u;
}
inline void ins_p(int f,int u,int c){
    tr[f].c[c]=u;tr[u].f=f;
}
inline void recnt(int u){
    tr[u].sum=w[u]^tr[tr[u].c[0]].sum^tr[tr[u].c[1]].sum;
}
inline bool isroot(int u){
    return tr[tr[u].f].c[0]!=u&&tr[tr[u].f].c[1]!=u;
}
inline void rotate(int u){
    int f=tr[u].f;bool c=son(u);
    if(isroot(f)) tr[u].f=tr[f].f;
    else ins_p(tr[f].f,u,son(f));
    ins_p(f,tr[u].c[c^1],c);
    ins_p(u,f,c^1);
    recnt(f);recnt(u);
}
inline void down(int u){
    if(tr[u].rev){
        tr[u].rev=0;
        swap(tr[u].c[0],tr[u].c[1]);
        tr[tr[u].c[0]].rev^=1;
        tr[tr[u].c[1]].rev^=1;
    }
}
inline void splay(int u){
    s.push(u);
    for(int v=u;!isroot(v);v=tr[v].f) s.push(tr[v].f);
    while(!s.empty()){
        down(s.top());s.pop();
    }
    while(!isroot(u)){
        if(isroot(tr[u].f)) rotate(u);
        else if(son(tr[u].f)==son(u)){
            rotate(tr[u].f);rotate(u);
        }
        else{
            rotate(u);rotate(u);
        }
    }
}
inline void access(int u){
    for(int lst=0;u;lst=u,u=tr[u].f){
        splay(u);tr[u].c[1]=lst;recnt(u);
        if(lst) tr[lst].f=u;
    }
}
//使u成为所在树的根节点
inline void makeroot(int u){
    access(u);splay(u);tr[u].rev^=1;
}
//找到u所在树的根节点
inline int findroot(int u){
    access(u);splay(u); 
    while(down(u),tr[u].c[0]) u=tr[u].c[0];
    splay(u);
    return u;
}
//u,v同一平衡树,u为v的左孩子 
inline void select(int u,int v){
    makeroot(u);access(v);splay(v);
}
inline void link(int u,int v){
    makeroot(u);tr[u].f=v;
}
inline void cut(int u,int v){
    select(u,v);tr[v].c[0]=tr[u].f=0;recnt(v);
}
inline void change(int u,int k){
    makeroot(u);w[u]=k;recnt(u);
}
inline void Aireen(){
    n=read();m=read();
    for(int i=1;i<=n;++i) tr[i].sum=w[i]=read();
    int ty,x,y;
    while(m--){
        ty=read();x=read();y=read();
        switch(ty){
            case 0:select(x,y);printf("%d\n",tr[y].sum);break;
            case 1:if(findroot(x)!=findroot(y)) link(x,y);break;
            case 2:if(findroot(x)==findroot(y)) cut(x,y);break;
            case 3:change(x,y);break;
        }
    }
}
int main(){
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    Aireen();
    fclose(stdin);
    fclose(stdout);
    return 0;
}

2017-04-06 21:50:07