rt

可能马蜂比较独特（自认为还性

#include<bits/stdc++.h>
using namespace std;
void solve();
int main(){solve();}
#define int long long
class LCT{
/*----------------- 节点 ------------------*/
struct Node
{
    int Fro;//父亲指向
    int To[2];//左右儿子
    int Rev;//翻转标记
    int Tag;//权值标记
    int Sum;//路径权值和
    int Siz;//辅助树上子树大小
    int Val;//点权
    inline void Rever(){
        To[0]^=To[1];
        To[1]^=To[0];
        To[0]^=To[1];
        Rev^=1;
    }
}T[500000];
/* ----------- 一般数据结构函数 ----------- */
void PushDown(int rt);
void PushUp(int rt);
/* 一----------- Splay树函数 -----------一 */
//#define catch(rt)  //获取 [rt] 是父亲的哪个儿子
void Rotate(int rt);//将 [rt] 向上旋转一层的操作
public:void Splay(int rt);//通过和 Rotate 操作联动实现把 [rt] 旋转到 当前 Splay 的根
/*--------------- NEW -------------------*/
/*^只有此操作是必须实现的，其他操作视题目而实现*/
int Access(int rt);//把从根到 [rt] 的所有点放在一条实链里，使根到 [rt] 成为一条实路径，并且在同一棵 Splay 里。
/*其他的LCT的独有函数*/
bool IsRoot(int rt);//判断 [rt] 是否是所在树的根
void Update(int rt);//在 Access 操作之后，递归地从上到下 PushDown 更新信息
void TurnRoot(int rt);//使 [rt] 点成为其所在树的根
public:
int query(int kl);//访问 T->sum 本题要用
void Cut(int x,int y);//把 [x, y] 两点间边删掉
void Link(int x,int y);//在 [x, y] 两点间连一条边
int Find(int x);//找到 [x] 所在树的根节点编号
void Fix(int kl,int val);//修改 [kl] 的点权为 [val] 
void Split(int x,int y);//提取出 [x, y] 间的路径，方便做区间操作
};
/*---------------- Push -----------------*/
void LCT::PushUp(int rt){
    T[rt].Sum=T[rt].Val^T[T[rt].To[0]].Sum^T[T[rt].To[1]].Sum;
}
void LCT::PushDown(int rt){
    if(T[rt].Rev){
        if(T[rt].To[0]){
            T[T[rt].To[0]].Rever();
        }   
        if(T[rt].To[1]){
            T[T[rt].To[1]].Rever();
        }
        T[rt].Rev=0;
    }
}
/*--------------- Train -----------------*/
#define catch(rt) (T[T[rt].Fro].To[1]==rt)

void LCT::Rotate(int rt){
    int F=T[rt].Fro;
    int Ff=T[F].Fro;
    int opt=catch(rt);
    if(!IsRoot(F)){
        T[Ff].To[catch(F)]=rt;
    }
    T[F].To[opt]=T[rt].To[!opt];
    T[T[rt].To[!opt]].Fro=F;
    T[rt].To[!opt]=F;
    T[F].Fro=rt;
    T[rt].Fro=Ff;
    PushUp(F);
    PushUp(rt);
}
void LCT::Splay(int rt){
    Update(rt);
    for(int F;F=T[rt].Fro,!IsRoot(rt);Rotate(rt)){
        if(!IsRoot(F)){
            Rotate(catch(F)==catch(rt)?F:rt);
        }
    }
}
bool LCT::IsRoot(int rt){
    return T[T[rt].Fro].To[0]!=rt&&T[T[rt].Fro].To[1]!=rt;
}
int LCT::Access(int rt){
    int P;
    for(P=0;rt;P=rt,rt=T[rt].Fro){
        Splay(rt);
        T[rt].To[1]=P;
        PushUp(rt);
    }
    return P;
}
void LCT::Update(int rt){
    if(!IsRoot(rt)){/////////////////////
        Update(T[rt].Fro);
    }
    PushDown(rt);
}
void LCT::TurnRoot(int rt){
    rt=Access(rt);
    Splay(rt);
    T[rt].Rever();
}
void LCT::Link(int x,int y){
    TurnRoot(x);
    // Splay(x);
    T[x].Fro=y;
}
void LCT::Cut(int x,int y){
    TurnRoot(x);
    Access(y);
    Splay(y);
    T[y].To[0]=T[x].Fro=0;
    PushUp(y);
}
int LCT::Find(int x){
    Access(x);
    Splay(x);
    // PushDown(x);
    while(T[x].To[0]){
        x=T[x].To[0];
        PushDown(x);
    }
    // Splay(x);
    return x;
}
void LCT::Fix(int kl,int val)
{
    T[kl].Val=val;
    // Splay(kl);
}
int LCT::query(int kl){
    return T[kl].Sum;
}
void LCT::Split(int x,int y){
    TurnRoot(x);
    Access(y);
    Splay(y);
}
/*-------------------solution-------------------*/
LCT L;
int n,Q;
void solve(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    cin>>n>>Q;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        L.Fix(i,x);
    }
    for(int i=1;i<=Q;i++){
        int opt,x,y;
        cin>>opt>>x>>y;
        switch(opt){
            case 0:
                L.Split(x,y);
                cout<<L.query(y)<<'\n';
            break;
            case 1:
                if(L.Find(x)!=L.Find(y)){
                    L.Link(x,y);
                }
            break;
            case 2:
                if(L.Find(x)==L.Find(y)){
                    L.Cut(x,y);
                }
            break;
            case 3:
                L.Fix(x,y);
                L.Splay(x);
            break;   
        }
    }
}