记录编号	415964	评测结果	AAAAAAAAAA
题目名称	可持久化线段树	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	0.318 s
提交时间	2017-06-19 00:00:54	内存使用	0.73 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<vector>
#include<algorithm>
#include<stack>
#include<string>
#include<cmath>
const int MAXN=1e5;
using namespace std;
struct pstree
{
	int mx;
	pstree *ls,*rs;
	pstree(){ls=rs=NULL;}
};
int n,q,mem;
int k,l,r,P,v;
int N[10001];
pstree *roots[MAXN];
pstree* build(int l,int r);
pstree* change(pstree *now,int l,int r);
int search(pstree *now,int l,int r,int nl,int nr);
int main()
{
	freopen("longterm_segtree.in","r",stdin);
	freopen("longterm_segtree.out","w",stdout);
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)scanf("%d",&N[i]);
	roots[++mem]=build(1,n);
	for(int i=1;i<=q;i++)
	{
		int temp;
		scanf("%d",&temp);
		if(temp)
		{
			scanf("%d%d%d",&k,&P,&v);
			roots[++mem]=change(roots[k],1,n);
		}
		else
		{
			scanf("%d%d%d",&k,&l,&r);
			printf("%d\n",search(roots[k],1,n,l,r));
		}
	}
	return 0;
}
pstree* change(pstree *now,int l,int r)
{
	pstree *p=new pstree();
	if(l==r)
	{
		p->mx=v;
		return p;
	}
	int mid=(l+r)>>1;
	if(P<=mid)
	{
		p->ls=change(now->ls,l,mid);
		p->rs=now->rs;
	}
	else
	{
		p->rs=change(now->rs,mid+1,r);
		p->ls=now->ls;
	} 
	p->mx=max(p->ls->mx,p->rs->mx);
	return p;
}
int search(pstree *now,int l,int r,int nl,int nr)
{
	if(l==nl&&r==nr)return now->mx;
	int mid=(l+r)>>1;
	if(nr<=mid)return search(now->ls,l,mid,nl,nr);
	if(nl>mid)return search(now->rs,mid+1,r,nl,nr);
	return max(search(now->ls,l,mid,nl,mid),search(now->rs,mid+1,r,mid+1,nr));
}
pstree* build(int l,int r)
{
	pstree *p=new pstree();
	if(l!=r)
	{
		int mid=(l+r)>>1;
		p->ls=build(l,mid);
		p->rs=build(mid+1,r);
		p->mx=max(p->ls->mx,p->rs->mx);
		return p;
	}
	p->mx=N[l];
	return p;
}