#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];//未改动,继承上一颗线段树 
		}
	}
}

Categories:

Tags:

No responses yet

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

近期评论
归档
分类