Top Tree 模板（咕）

Sone1 调不动了，所以是 lg P3690。

写着写着就不知道自己写的是 AAAT 还是 SATT 了，反正能用。

#include <iostream>
#include <vector>
#include <cassert>
#define UP(i,s,e) for(auto i=s; i<e; ++i)
using std::cin; using std::cout;
constexpr int N = 1e5, M = 3e5;
namespace TopTree{ // }{{{
struct Modify_tag{
    int val; bool modi;
    Modify_tag(){}
    Modify_tag(int v, bool t):val(v), modi(t){}
    Modify_tag operator>>=(Modify_tag b){
        if(b.modi) *this = b;
        else val += b.val;
        return *this;
    }
};
enum NodeType{ RAKE, COMPRESS };
using NT = NodeType;
struct Node{
    Node *fa;
    Node *ls, *ms, *rs;
    NT typ;
    int val, hsum, lsum; // heavysum, lightsum
    bool rev;
} nil_, *const nil = &nil_, nds[N*2];
std::vector<int> rubbish; int nodcnt = 0;
Node *nnod(){
    if(!rubbish.empty()){
        Node *p = nds + rubbish.back();
        rubbish.pop_back();
        return p;
    } else {
        return nds + nodcnt++;
    }
}
void erase(Node *x){ rubbish.push_back(x - nds); }
void flip(Node *x){ if(x != nil) x->rev ^= 1; }
void pushrev(Node *x){ 
    if(x == nil || x->typ == RAKE) return;
    if(!x->rev) return;
    std::swap(x->ls, x->rs);
    x->rev ^= 1;
    flip(x->ls);
    flip(x->rs);
}
void pushup(Node *x){
    if(x == nil) return;
    pushrev(x);
    if(x->typ == RAKE){
        x->lsum = x->ls->lsum ^ x->ms->lsum ^ x->rs->lsum;
    } else {
        x->hsum = x->ls->hsum ^ x->rs->hsum ^ x->val;
        x->lsum = x->ls->lsum ^ x->ms->lsum ^ x->rs->lsum ^ x->val;
    }
}
void pushdown(Node *x){ pushrev(x); }
bool nroot(Node *x){ return x == x->fa->ls or x == x->fa->rs; }
bool isrs(Node *x){ return x == x->fa->rs; }
void pushdddd(Node *x){
    if(x == nil) return;
    if(nroot(x)) pushdddd(x->fa);
    pushdown(x);
}
void setfa(Node *x, Node *f, int which){
    if(x != nil) x->fa = f;
    if(which == 0) f->ls = x;
    else if(which == 1) f->rs = x;
    else f->ms = x;
}
void rotate(Node *x){
    if(x == nil || !nroot(x)) return;
    Node *y = x->fa, *z = y->fa;
    if(z != nil){
        if(z->ls == y) z->ls = x;
        else if(z->ms == y) z->ms = x;
        else if(z->rs == y) z->rs = x;
    }
    if(x == y->ls){
        setfa(x->rs, y, 0);
        x->rs = y;
    } else {
        setfa(x->ls, y, 1);
        x->ls = y;
    }
    y->fa = x; x->fa = z;
    pushup(y);
    pushup(x);
}
void splay(Node *x, Node *to = nil){
    if(x == nil) return;
    pushdddd(x);
    for(Node *y; y = x->fa, nroot(x) && y!=to; rotate(x)){
        if(y->fa != to && nroot(y)){
            rotate(isrs(x) ^ isrs(y) ? x : y);
        }
    }
}
void unuse(Node *x){
    if(x == nil) return;
    assert(x->typ == RAKE);
    setfa(x->ms, x->fa, 1);
    x->ms = nil;
    if(x->ls != nil){
        Node *p = x->ls;
        pushdown(p);
        while(p->rs != nil) p = p->rs, pushdown(p);
        splay(p, x);
        setfa(x->rs, p, 1);
        setfa(p, x->fa, 2);
        pushup(p);
        pushup(x->fa);
    } else {
        setfa(x->rs, x->fa, 2);
    }
    erase(x);
}
void splice(Node *x){ 
    if(x == nil) return;
    assert(x->typ == RAKE);
    splay(x);
    Node *y = x->fa;
    splay(y);
    pushdown(x);
    if(y->rs != nil){
        std::swap(x->ms->fa, y->rs->fa);
        std::swap(x->ms, y->rs);
        pushup(x);
    } else {
        unuse(x);
    }
    pushup(y);
}
void access(Node *x){
    if(x == nil) return;
    splay(x);
    if(x->rs != nil){
        Node *y = nnod();
        y->val = 0;
        y->rev = 0;
        y->hsum = y->lsum = 0;
        setfa(x->ms, y, 0);
        setfa(x->rs, y, 2); x->rs = nil;
        setfa(y, x, 2);
        y->rs = nil;
        y->typ = RAKE;
        pushup(y);
        pushup(x);
    }
    Node *p = x;
    while(p->fa != nil){
        splice(p->fa);
        p = p->fa;
        pushup(p);
    }
    splay(x);
}
void mkroot(Node *x){ access(x); flip(x); }
void expose(Node *x, Node *y){ mkroot(x); access(y); }
Node *findrt(Node *x){
    access(x);
    pushdown(x);
    while(x->ls != nil) x = x->ls, pushdown(x);
    splay(x);
    return x;
}
void link(Node *x, Node *y){
    if(findrt(x) == findrt(y)) return;
    access(x);
    mkroot(y);
    setfa(y, x, 1);
    pushup(x);
}
void cut(Node *x, Node *y){
    expose(x, y);
    if(y->ls != x || x->rs != nil) return;
    x->fa = y->ls = nil;
    pushup(y);
}
} // {}}}
namespace m{ // }{{{
constexpr int N = 1e5;
int in, im;
using TopTree::Node;
Node *ndid[N];
void work(){
    cin >> in >> im;
    UP(i, 0, in){
        int x; cin >> x;
        Node *p = TopTree::nnod();
        p->ls = p->ms = p->rs = p->fa = TopTree::nil;
        p->val = p->hsum = p->lsum = x;
        p->typ = TopTree::COMPRESS;
        p->rev = false;
        ndid[i] = p;
    }
    UP(i, 0, im){
        int op, x, y;
        cin >> op >> x >> y;
        switch(op){
            case 0:
                x--, y--;
                if(TopTree::findrt(ndid[x]) != TopTree::findrt(ndid[y])){
                    cout << 0 << '\n';
                } else {
                    TopTree::expose(ndid[x], ndid[y]);
                    cout << ndid[y]->hsum << '\n';
                }
                break;
            case 1:
                x--, y--;
                TopTree::link(ndid[x], ndid[y]);
                break;
            case 2:
                x--, y--;
                TopTree::cut(ndid[x], ndid[y]);
                break;
            case 3:
                x--;
                TopTree::mkroot(ndid[x]);
                ndid[x]->val = y;
                TopTree::pushup(ndid[x]);
                break;
            default:;
        }
    }
}
} // {}}}
int main(){std::ios::sync_with_stdio(0); cin.tie(0); m::work(); return 0;}