【P3319】题解
一：【题意】
略
二：【解法】
略
三：【代码】
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=4*N+log2(N)*N;
int a[N];
int rt[N];
struct node{int l,r;int sum;int son[2];#define l(q) tree[q].l#define r(q) tree[q].r#define sum(q) tree[q].sum#define ls(q) tree[q].son[0]#define rs(q) tree[q].son[1]
}tree[M];
int cnt;
void build(int &q,int l,int r){if(q==0) q=++cnt;l(q)=l;r(q)=r;if(l==r){sum(q)=a[l];return ;}int mid=l+r>>1;build(ls(q),l,mid);build(rs(q),mid+1,r);
}
void update(int las,int &now,int tp,int d){if(now==0) now=++cnt;tree[now]=tree[las];int l=l(las),r=r(las);if(l==r){sum(now)=d;return ;}int mid=l+r>>1;bool s=(tp>mid);update(tree[las].son[s],tree[now].son[s]=0,tp,d);
}
int query(int q,int tp){int l=l(q),r=r(q);if(l==r) return sum(q);int mid=l+r>>1;if(tp<=mid) return query(ls(q),tp);else return query(rs(q),tp);
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,m;cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];build(rt[0],1,n);for(int i=1;i<=m;i++){int pre,op,p;cin>>pre>>op>>p;if(op==1){int d;cin>>d;update(rt[pre],rt[i],p,d);}else{rt[i]=rt[pre];cout<<query(rt[pre],p)<<"\n";}}return 0;
}