题面：

不知道说啥，总之我挺喜欢自己打的板子的！

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 inline int rd(){ 6     int x=0,f=1;char c=getchar(); 7     while(c<'0'||c>'9'){
   if(c=='-')f=-1; c=getchar();} 8     while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();} 9     return f*x;10 }11 const int maxn=(1e6)+50,maxm=maxn;12 int N,M,num_treenode=0,root[maxm],belong_root[maxm],num_root=0,u,num_version=0,A[maxn],V,loc,o,val;13 struct Tree{14     int ls,rs,l,r,data;15 }t[(maxn<<2)+22*maxm];16 inline void Build(int x,int l,int r){17     t[x].l=l;t[x].r=r;18     if(l==r){19         t[x].data=A[l];20         return;21     }22     int mid=(l+r)>>1;23     t[x].ls=++num_treenode;Build(num_treenode,l,mid);24     t[x].rs=++num_treenode;Build(num_treenode,mid+1,r);25     return;26 }27 inline void Update(int x,int u,int loc,int v){28     int l=t[u].l,r=t[u].r,mid=(l+r)>>1;29     t[x].l=l;t[x].r=r;30     if(l==r&&l==loc){31         t[x].data=v;32         return;33     }34     if(loc<=mid){35         t[x].rs=t[u].rs;36         t[x].ls=++num_treenode;37         Update(num_treenode,t[u].ls,loc,v);38     }39     else{40         t[x].ls=t[u].ls;41         t[x].rs=++num_treenode;42         Update(num_treenode,t[u].rs,loc,v);43     }44     return;45 }46 inline int Query(int x,int loc){47     int l=t[x].l,r=t[x].r,mid=(l+r)>>1;48     if(l==r&&l==loc) return t[x].data;49     if(loc<=mid)return Query(t[x].ls,loc);50     else return Query(t[x].rs,loc);51 }52 int main(){53     N=rd();M=rd();54     for(int i=1;i<=N;i++)A[i]=rd();55     root[++num_root]=++num_treenode;//root[i]数组记录树i的根节点是哪个 56     belong_root[0]=num_root;//belong_root[i]记录版本i的树根是哪个 57     Build(num_treenode,1,N);58     while(M--){59         V=rd();o=rd();loc=rd();60         u=belong_root[V];//u记录第V个版本到底属于哪颗树 61         if(o==1){62             val=rd();63             root[++num_root]=++num_treenode;//多了一颗树 64             Update(num_treenode,root[u],loc,val);65             belong_root[++num_version]=num_root;66         }67         else{68             printf("%d\n",Query(root[u],loc));69             belong_root[++num_version]=u;70         } 71     }72     return 0;73 }
       
      
     

---

By:AlenaNuna