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;}