Zhengxi Liu's Blog

#include<bits/stdc++.h>
using namespace std;

#define ls(x) T[x].son[0]
#define rs(x) T[x].son[1]
#define fa(x) T[x].p
#define not_rt(x) ls(fa(x)) == x || rs(fa(x)) == x

const int N = 1e5 + 7;

struct node{
    int son[2], p, sum, v;
    bool tag;
}T[N];

int n, m, op, x, y;

void push_up(int k){
    T[k].sum = T[ls(k)].sum ^ T[rs(k)].sum ^ T[k].v;
}

void push_down(int k){
    if(!T[k].tag) return;
    swap(ls(k), rs(k));
    T[ls(k)].tag ^= 1;
    T[rs(k)].tag ^= 1;
    T[k].tag = 0;
}

void rotate(int k){
    int p = fa(k), gp = fa(p);
    bool op = rs(p) == k;
    if(not_rt(p)) T[gp].son[rs(gp) == p] = k; // virtual father cannot point to son
    fa(k) = gp, fa(p) = k;
    T[p].son[op] = T[k].son[op ^ 1];
    fa(T[k].son[op ^ 1]) = p;
    T[k].son[op ^ 1] = p;
    push_up(p), push_up(k);
}

void push_all(int k){
    if(not_rt(k)) push_all(fa(k));
    push_down(k);
}

void splay(int k){
    push_all(k); // son left/right order must be correct in order to splay correctly
    while(not_rt(k)){
        int p = fa(k), gp = fa(p);
        if(not_rt(p)){
            if(ls(p) == k ^ ls(gp) == p) rotate(k);
            else rotate(p);
        }
        rotate(k);
    }
}

void access(int k){ // establish real edge all the way to root
    for(int y = 0; k; ){
        splay(k); // move current node to the root of the current splay tree
        rs(k) = y;
        // Two moves in one:
        // 1. unbind the real edge that used to be at rs, so there are no nodes with depth greater than the initial k
        // 2. connect the other previous nodes that is above the initial k to this node
        push_up(k);
        y = k, k = fa(k);
    }
}

void make_rt(int k){
    access(k);
    splay(k);
    T[k].tag ^= 1;
    // the node k is moved to the root, but in the in-order travesal, it is still the deepest node
    // thus, we need to mandatorily reorder the tree, so that the deepest node is shallowest, and vice versa
    // (all the nodes left of k is shallower than k, right is deeper)
}

void split(int x, int y){
    make_rt(x); // make x the root of every node
    access(y); // let x and y be in the same splay tree
    splay(y); // prevent possible tle
}

int find_rt(int k){
    access(k);
    splay(k);
    while(ls(k)) // must include push_down!!!
        push_down(k), k = ls(k);
    splay(k);
    return k;
}

void link(int x, int y){
    make_rt(x);
    if(find_rt(y) != x) fa(x) = y;
}

void cut(int x, int y){
    make_rt(x);
    if(find_rt(y) == x && fa(y) == x && !ls(y)){
        // !ls(y) means there are no nodes that are stuck between the depth of x and y
        rs(x) = fa(y) = 0;
        push_up(x);
    }
}

int main(){

    cin >> n >> m;

    for(int i = 1; i <= n; i ++){
        cin >> x;
        T[i].v = T[i].sum = x;
    }

    while(m --){

        cin >> op >> x >> y;

        if(!op) split(x, y), cout << T[y].sum << endl;
        if(op == 1) link(x, y);
        if(op == 2) cut(x, y);
        if(op == 3) splay(x), T[x].v = y, push_up(x); // must push_up!!!

    }

    return 0;
}