记录编号	454770	评测结果	AAAAAAAAAA
题目名称	可持久化线段树	最终得分	100
用户昵称	Hzoi_QTY	是否通过	通过
代码语言	C++	运行时间	0.351 s
提交时间	2017-09-29 16:53:02	内存使用	0.73 MiB

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 10005
using namespace std;
int n,m,tot=1,a[N];
namespace chairtree
{
	struct tree
	{
		tree* lc;tree* rc;
		int h;
		tree(){h=0;lc=rc=NULL;}
		void updata(){h=max(lc->h,rc->h);}
	}*null=new tree(),*root[N*10];
	tree* newtree()
	{
		tree* o=new tree();
		o->lc=o->rc=null;o->h=0;
		return o;
	}
	void build(int l,int r,tree* &x)
	{
		x=newtree();
		if(l==r){x->h=a[l];return;}
		int mid=l+r>>1;
		build(l,mid,x->lc);
		build(mid+1,r,x->rc);
		x->updata();
	}
	void insert(int l,int r,tree* &x,tree* pre,int h,int k)
	{	
		if(l==r){x=newtree();x->h=k;return;}
		int mid=l+r>>1;
		if(h<=mid)
		{
			x->lc=newtree();x->rc=pre->rc;
			insert(l,mid,x->lc,pre->lc,h,k);
		}
		else
		{
			x->lc=pre->lc;x->rc=newtree();
			insert(mid+1,r,x->rc,pre->rc,h,k);
		}
		x->updata();
	}
	int q(int L,int R,int l,int r,tree* x)
	{
		if(L>=l&&R<=r){return x->h;}
		int mid=L+R>>1,s=0;
		if(l<=mid)s=q(L,mid,l,r,x->lc);
		if(r>mid)s=max(s,q(mid+1,R,l,r,x->rc));
		return s;
	}
}
using namespace chairtree;
int main()
{
	freopen("longterm_segtree.in","r",stdin);
	freopen("longterm_segtree.out","w",stdout);
	cin>>n>>m;int l,r,k,z;null->lc=null->rc=null;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	build(1,n,root[1]);
	while(m--)
	{
		scanf("%d%d%d%d",&z,&k,&l,&r);
		if(z==1)
			root[++tot]=newtree(),insert(1,n,root[tot],root[k],l,r);
		else
			printf("%d\n",q(1,n,l,r,root[k]));
	}
}