BZOJ 3282 Tree

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3282

题意:略。

思路:还是LCT模板题,因为异或具有交换律,所以splay的时候不会有影响。

#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define Key_Value ch[ch[root][1]][0]
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=300000+5;
const int INF=0x3f3f3f3f;
const int P=1000000007;
const double PI=acos(-1.0);
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
int n,m,op,x,y;
struct Link_Cut_Tree{
    int fa[maxn],ch[maxn][2],sum[maxn],val[maxn],q[maxn],top;bool rev[maxn];
    Link_Cut_Tree(){
        top=0;memset(fa,0,sizeof(fa));
        memset(ch,0,sizeof(ch));
        memset(rev,false,sizeof(rev));
    }
    bool isroot(int x){return !fa[x]||ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
    void UpdateRev(int x){
        if(!x)return;
        swap(ch[x][0],ch[x][1]);
        rev[x]^=1;
    }
    void pushdown(int x){
        if(rev[x]){
            UpdateRev(ch[x][0]);
            UpdateRev(ch[x][1]);
            rev[x]=0;
        }
    }
    void pushup(int x){
        sum[x]=sum[ch[x][0]]^sum[ch[x][1]]^val[x];
    }
    void Rotate(int x){
        int y=fa[x],kind=ch[y][1]==x;
        ch[y][kind]=ch[x][kind^1];
        fa[ch[y][kind]]=y;
        if (fa[y]){
            int z=fa[y];
            if (ch[z][0]==y) ch[z][0]=x;else if (ch[z][1]==y) ch[z][1]=x;
        }
        fa[x]=fa[y];fa[y]=x;ch[x][kind^1]=y;
        pushup(y);
    }
    void splay(int x){
        q[top=1]=x;
        for (int i=x;!isroot(i);i=fa[i]) q[++top]=fa[i];
        while (top) pushdown(q[top--]);
        while(!isroot(x)){
            int y=fa[x],z=fa[y];
            if (!isroot(y)){
                if ((ch[y][0]==x)^(ch[z][0]==y)) Rotate(x);
                else Rotate(y);
            }
            Rotate(x);
        }
        pushup(x);
    }
    void access(int x){for(int t=0;x;t=x,x=fa[x])splay(x),ch[x][1]=t,pushup(x);}
    void makeroot(int x){access(x);splay(x);UpdateRev(x);}
    void link(int x,int y){makeroot(x);fa[x]=y;access(x);}
    void split(int x,int y){makeroot(x);access(y);splay(y);}
    void cut(int x,int y){split(x,y);fa[ch[y][0]]=0;ch[y][0]=0;pushup(y);}
    int find(int x){
        access(x);splay(x);int y=x;
        while (ch[y][0]) y=ch[y][0];
        return y;
    }
    int ask(int x,int y){split(x,y);return sum[y];}
}T;
int main(){
    read(n),read(m);
    for (int i=1;i<=n;i++) T.sum[i]=read(T.val[i]);
    for (int i=1;i<=m;i++){
        read(op),read(x),read(y);
        if (op==0){
            printf("%d\n",T.ask(x,y));
        }
        else if (op==1){
            int tx=T.find(x),ty=T.find(y);
            if (tx!=ty) T.link(x,y);
        }
        else if (op==2){
            int tx=T.find(x),ty=T.find(y);
            if (tx==ty) T.cut(x,y);
        }
        else{
            T.makeroot(x);
            T.val[x]=y;
            T.pushup(x);
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注