记录编号	351614	评测结果	AAAAAAAAAA
题目名称	可持久化线段树	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.272 s
提交时间	2016-11-16 17:38:56	内存使用	38.82 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=50010;
void build(int,int,int&);
void modify(int,int,int&,int);
void qmax(int,int,int);
int mx[maxn<<6],lc[maxn<<6],rc[maxn<<6],root[maxn*10],cnt=0;
int n,m,s,t,k,x,d,ans,now=1;
int main(){
#define MINE
#ifdef MINE
	freopen("longterm_segtree.in","r",stdin);
	freopen("longterm_segtree.out","w",stdout);
#endif
	scanf("%d%d",&n,&m);
	build(1,n,root[1]);
	while(m--){
		scanf("%d%d",&d,&k);
		if(d){
			scanf("%d%d",&x,&d);
			modify(1,n,root[++now],root[k]);
		}
		else{
			scanf("%d%d",&s,&t);
			ans=1<<31;
			qmax(1,n,root[k]);
			printf("%d\n",ans);
		}
	}
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#endif
	return 0;
}
void build(int l,int r,int &rt){
	rt=++cnt;
	if(l==r){
		scanf("%d",&mx[rt]);
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,lc[rt]);
	build(mid+1,r,rc[rt]);
	mx[rt]=max(mx[lc[rt]],mx[rc[rt]]);
}
void modify(int l,int r,int &rt,int pr){
	rt=++cnt;
	if(l==r){
		mx[rt]=d;
		return;
	}
	lc[rt]=lc[pr];rc[rt]=rc[pr];
	int mid=(l+r)>>1;
	if(x<=mid)modify(l,mid,lc[rt],lc[pr]);
	else modify(mid+1,r,rc[rt],rc[pr]);
	mx[rt]=max(mx[lc[rt]],mx[rc[rt]]);
}
void qmax(int l,int r,int rt){
	if(s<=l&&t>=r){
		ans=max(ans,mx[rt]);
		return;
	}
	int mid=(l+r)>>1;
	if(s<=mid)qmax(l,mid,lc[rt]);
	if(t>mid)qmax(mid+1,r,rc[rt]);
}