代码:
#include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 4; struct T { int l,r,v; }t[maxn*40]; int a[maxn],edition[maxn*40],tot; int build(int l,int r) { int p=++tot; if(l==r) { t[p].v=a[l]; return p; } int mid=(l+r)>>1; t[p].l=build(l,mid); t[p].r=build(mid+1,r); return p; } int update(int id,int l,int r,int k,int val) { int p=++tot; if(l==r) { t[p].v=val; return p; } int mid=(l+r)>>1; t[p].l=t[id].l,t[p].r=t[id].r; if(k<=mid) t[p].l=update(t[p].l,l,mid,k,val); else t[p].r=update(t[p].r,mid+1,r,k,val); return p; } int query(int id,int l,int r,int k) { if(l==r) return t[id].v; int mid=(l+r)>>1; if(k<=mid) return query(t[id].l,l,mid,k); else return query(t[id].r,mid+1,r,k); } int main() { int n,m,id,op,k,val; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,n); edition[0]=1; for(int i=1;i<=m;i++) { scanf("%d%d%d",&id,&op,&k); if(op==1) { scanf("%d",&val); edition[i]=update(edition[id],1,n,k,val); } else { edition[i]=edition[id]; printf("%d\n",query(edition[id],1,n,k)); } } return 0; }