BZOJ_3282_Tree

BZOJ_3282_Tree_LCT

Description

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

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

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

保证ｘ到ｙ是联通的。

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

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

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

Input

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

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

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

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

Output

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

Sample Input

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

Sample Output

3
1

LCT维护一下点权的xor和，单点修改直接暴力。

修改的时候应该是不用access，但我加上access操作会快一些

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

#define N 300050

#define ls ch[p][0]

#define rs ch[p][1]

#define get(x) (ch[f[x]][1]==x)

int ch[N][2],f[N],sum[N],n,m,val[N],rev[N];

inline bool isrt(int p) {

    return ch[f[p]][1]!=p&&ch[f[p]][0]!=p;

}

inline void pushdown(int p) {

    if(rev[p]) {

        swap(ch[ls][0],ch[ls][1]);

        swap(ch[rs][0],ch[rs][1]);

        rev[ls]^=1; rev[rs]^=1;

        rev[p]=0;

    }

}

inline void pushup(int p) {

    sum[p]=sum[ls]^sum[rs]^val[p];

}

inline void update(int p) {

    if(!isrt(p)) update(f[p]);

    pushdown(p);

}

void rotate(int x) {

    int y=f[x],z=f[y],k=get(x);

    if(!isrt(y)) ch[z][ch[z][1]==y]=x;

    ch[y][k]=ch[x][!k]; f[ch[y][k]]=y;

    ch[x][!k]=y; f[y]=x; f[x]=z;

    pushup(y); pushup(x);

}

void splay(int x) {

    update(x);

    for(int fa;fa=f[x],!isrt(x);rotate(x))

        if(!isrt(fa))

            rotate(get(fa)==get(x)?fa:x);

}

void access(int p) {

    int t=0;

    while(p) splay(p),rs=t,pushup(p),t=p,p=f[p];

}

void makeroot(int p) {

    access(p); splay(p);

    swap(ls,rs); rev[p]^=1;

}

void link(int x,int p) {

    makeroot(x); f[x]=p;

}

void cut(int x,int p) {

    makeroot(x); access(p); splay(p); ls=f[x]=0;

}

int find(int p) {

    access(p); splay(p);

    while(ls) pushdown(p),p=ls;

    return p;

}

void fix(int x,int v) {

    /*access(x);*/ splay(x); sum[x]^=val[x]; val[x]=v; sum[x]^=val[x];

}

int main() {

    scanf("%d%d",&n,&m);

    int i,x,y,opt;

    for(i=1;i<=n;i++) scanf("%d",&val[i]);

    for(i=1;i<=m;i++) {

        scanf("%d%d%d",&opt,&x,&y);

        if(opt==0) {

            makeroot(x); access(y); splay(y);

            printf("%d\n",sum[y]);

        }else if(opt==1) {

            int t1=find(x),t2=find(y);

            if(t1!=t2) link(x,y);

        }else if(opt==2) {

            int t1=find(x),t2=find(y);

            if(t1==t2) cut(x,y);

        }else {

            fix(x,y);

        }

    }

}

巴特西