不知道说啥，总之我挺喜欢自己打的板子的！
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
inline int rd(){
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return f*x;
}
const int maxn=(1e6)+,maxm=maxn;
int N,M,num_treenode=,root[maxm],belong_root[maxm],num_root=,u,num_version=,A[maxn],V,loc,o,val;
struct Tree{
int ls,rs,l,r,data;
}t[(maxn<<)+*maxm];
inline void Build(int x,int l,int r){
t[x].l=l;t[x].r=r;
if(l==r){
t[x].data=A[l];
return;
}
int mid=(l+r)>>;
t[x].ls=++num_treenode;Build(num_treenode,l,mid);
t[x].rs=++num_treenode;Build(num_treenode,mid+,r);
return;
}
inline void Update(int x,int u,int loc,int v){
int l=t[u].l,r=t[u].r,mid=(l+r)>>;
t[x].l=l;t[x].r=r;
if(l==r&&l==loc){
t[x].data=v;
return;
}
if(loc<=mid){
t[x].rs=t[u].rs;
t[x].ls=++num_treenode;
Update(num_treenode,t[u].ls,loc,v);
}
else{
t[x].ls=t[u].ls;
t[x].rs=++num_treenode;
Update(num_treenode,t[u].rs,loc,v);
}
return;
}
inline int Query(int x,int loc){
int l=t[x].l,r=t[x].r,mid=(l+r)>>;
if(l==r&&l==loc) return t[x].data;
if(loc<=mid)return Query(t[x].ls,loc);
else return Query(t[x].rs,loc);
}
int main(){
N=rd();M=rd();
for(int i=;i<=N;i++)A[i]=rd();
root[++num_root]=++num_treenode;//root[i]数组记录树i的根节点是哪个
belong_root[]=num_root;//belong_root[i]记录版本i的树根是哪个
Build(num_treenode,,N);
while(M--){
V=rd();o=rd();loc=rd();
u=belong_root[V];//u记录第V个版本到底属于哪颗树
if(o==){
val=rd();
root[++num_root]=++num_treenode;//多了一颗树
Update(num_treenode,root[u],loc,val);
belong_root[++num_version]=num_root;
}
else{
printf("%d\n",Query(root[u],loc));
belong_root[++num_version]=u;
}
}
return ;
}
By:AlenaNuna