#include<cstdio>
#define MAXN 15000000
//15倍空间...
struct node {
int l,r,val;
} tree[MAXN];
int sav[15000000],M,N;
int top,root[15000000];
int New(int n) {
//注意:n节点先被复制再被重新赋值(return)
top++;//top存储新节点的位置
tree[top]=tree[n];
return top;
}
int make_tree(int n,int l,int r) {
n=++top;//获取存节点的位置
if(l==r) {
tree[n].val=sav[l];
return n;
}
int mid=(l+r)>>1;
tree[n].l=make_tree(tree[n].l,l,mid);
tree[n].r=make_tree(tree[n].r,mid+1,r);
return n;
}
int update(int n,int l,int r,int target,int val) {
n=New(n);//建新树,n先被复制再被重新赋值
if(l==r) {
tree[n].val=val;//Target Reached
} else {
int mid=(l+r)>>1;
if(target<=mid) {//需要就建立新树
tree[n].l=update(tree[n].l,l,mid,target,val);
} else {
tree[n].r=update(tree[n].r,mid+1,r,target,val);
}
}
return n;//新(子)树的root
}
int query(int n,int l,int r,int target) {
if(l==r)return tree[n].val;
int mid=(l+r)>>1;
if(target<=mid) {
return query(tree[n].l,l,mid,target);
} else {
return query(tree[n].r,mid+1,r,target);
}
}
int read() {
int x=0,f=1;
char ch;
do {
ch=getchar();
if(ch=='-')f=-1;
} while(ch<'0'||ch>'9');
do {
x=10*x+ch-'0';
ch=getchar();
} while(ch>='0'&&ch<='9');
return f*x;
}
int main() {
N=read(),M=read();
for(int i=1;i<=N;i++)sav[i]=read();
root[0]=make_tree(0,1,N);//root[i]存储版本i的树根
for(int i=1;i<=M;i++){
//对于l,r的问题:l,r只用于修改/查询时,传递节点的控制范围(log2)
//update(n,,,,)/query(n,,,)中的n初始是树根,传递中是子树树根
int ver=read(),d=read();
if(d==1){
int x=read(),val=read();
root[i]=update(root[ver],1,N,x,val);
//新节点是老节点的update
}else{
int loc=read();
printf("%dn",query(root[ver],1,N,loc));
root[i]=root[ver];//未改动,继承上一颗线段树
}
}
}
No responses yet