40分WA求调 P3919 【模板】可持久化线段树 1（可持久化数组）

#include<bits/stdc++.h>
#define WA AC 
//#define int  long long
#define maxn 5000031

using namespace std;
int n,m,a[1000005],l,r,t,k,tmp,x,y,s[1000005],cnt=1,cnt2=0;
struct node{
	int v,left,right;
}segtree[2000000*21];

void build(int l,int r,int rt){
	//segtree[rt].lzy=0;
	if(l==r){
		segtree[rt].v=a[l];
		segtree[rt].left=0;
		segtree[rt].right=0;
		return;
	}
	int m=(l+r)>>1;
	segtree[rt].left=++cnt;
	segtree[rt].right=++cnt;
	build(l,m,segtree[rt].left);
	build(m+1,r,segtree[rt].right);
}
//int query(int x,int l,int r,int rt){
//	if(x>r || y<l) return 0;
//	if(r<=y && x<=l){
//		return segtree[rt].v;
//	}
//	int m=(l+r)>>1;
//	//pushdown(m-l+1,r-m,rt);
//	return query(x,y,l,m,rt<<1)+query(x,y,m+1,r,rt<<1|1);
//}
void update(int x,int y,int l,int r,int rt,int rtt){
	if(l==r){
		segtree[rtt].v=y;
		return;
	}
	int m=(l+r)>>1;
	
	if(x<=m){
		segtree[rtt].left=++cnt;
		update(x,y,l,m,segtree[rt].left,segtree[rtt].left);
		segtree[rtt].right=segtree[rt].right;
		
	} 
	else{
		segtree[rtt].right=++cnt;
		update(x,y,m+1,r,segtree[rt].right,segtree[rtt].right);
		segtree[rtt].left=segtree[rt].left;
	}
	
}
int tofind(int x,int l,int r,int rt){
	if(l==r) return segtree[rt].v; 
	int m=(l+r)>>1;
	if(x<=m){
		return tofind(x,l,m,segtree[rt].left);
	} 
	else{
		return tofind(x,m+1,r,segtree[rt].right);
	}
}
void print(int rt){
	if(!rt) return;
	cout<<segtree[rt].v<<" ";
	print(segtree[rt].left);
	print(segtree[rt].right);
	
}
signed main(){
	s[0]=1;
	scanf("%d",&n);
	cin>>t;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	build(1,n,1);
	//print(1);
	
	for(int i=1;i<=t;i++){
		scanf("%d",&k);
		scanf("%d",&y);
		scanf("%d",&x);
		s[++cnt2]=++cnt;
		
		if(y==1){
			cin>>tmp;
			update(x,tmp,1,n,s[k],cnt);
			
		}
		else{
			segtree[cnt].right=segtree[s[cnt2-1]].right;
			segtree[cnt].left=segtree[s[cnt2-1]].left;
			int ans=tofind(x,1,n,s[k]);
			cout<<ans<<"\n";
		}
		//print(s[cnt2]);
	}
	
	
		
	return 0;
}