主席树求调

#include<bits/stdc++.h>
using namespace std;
long long n,m;
long long ans;
long long k;
long long bb,loc,val,tot=0;
long long rt,mode,x,y;
long long o;
long long a[2300005],t[2300005];
long long top=0;
struct node{
	long long l,r,date;
}tree[41151400];
long long kd(long long p){
	top++;
	tree[top]=tree[p];
	return top;
}
long long build(long long p,long long l,long long r){
	p=++top;
	if(l==r){
		tree[p].date=a[l];
		return p;
	}
	long long mid=(l+r)>>1;
	tree[p].l=build(tree[p].l,l,mid);
	tree[p].r=build(tree[p].r,mid+1,r);
	return p;
}
long long update(long long rt,long long l,long long r,long long k,long long val){
	rt=kd(rt);
	if(l==r){
		tree[rt].date=val;
		return rt;
	}
	else{
		long long mid=(l+r)>>1;
		if(k<=mid)tree[rt].l=update(tree[rt].l,l,mid,k,val);
		else tree[rt].l=update(tree[rt].r,mid+1,r,k,val);
	}
	return rt;
}
long long ask(long long p,long long l,long long r,long long k){
	if(l==r){
		return tree[p].date;
	}
	else{
		long long mid=(l+r)>>1;
		if(k<=mid) return ask(tree[p].l,l,mid,k);
		else return ask(tree[p].r,mid+1,r,k);
	}
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(long long i=1;i<=n;i++) scanf("%lld",&a[i]);
	t[0]=build(0,1,n);
	for(long long i=1;i<=m;i++){
		scanf("%lld%lld",&bb,&o);
		if(o==1){
			scanf("%lld%lld",&loc,&val);
			t[i]=update(t[bb],1,n,loc,val);
		}
		else{
			scanf("%lld",&loc);
			printf("%lld\n",ask(t[bb],1,n,loc));
			t[i]=t[bb];
		}
	}
}