记录编号	493837	评测结果	AAAAAAAAAA
题目名称	可持久化线段树	最终得分	100
用户昵称	nonamenotitle	是否通过	通过
代码语言	C++	运行时间	0.513 s
提交时间	2018-04-05 12:21:04	内存使用	21.27 MiB

#include <bits/stdc++.h>
using namespace std;
inline int readInt()
{
	char c; int tmp=0,x=1; c=getchar();
	while(c>'9' || c<'0') {if(c=='-') x=-1; c=getchar();}
	while(c>='0' && c<='9') {tmp=tmp*10+c-'0'; c=getchar();}
	return tmp*x;
}
const int maxn=(int)1e4+5;
const int maxq=(int)1e5+5;
int n,Q;
int a[maxn],rot[maxq];
int maxv[(maxn<<2)*50],tot=0,lson[(maxn<<2)*50],rson[(maxn<<2)*50];
int newNode(int val,int ls,int rs)
{
	tot++;
	maxv[tot]=val;
	lson[tot]=ls,rson[tot]=rs;
	return tot;
}
void build(int &o,int l,int r)
{
	if(l>r) return;
	o=++tot;
	if(l==r) {
		maxv[o]=a[l]; return;
	}else {
		int mid=(l+r)>>1;
		build(lson[o],l,mid); build(rson[o],mid+1,r);
		maxv[o]=max(maxv[lson[o]],maxv[rson[o]]);
	}
}
int Ins(int prert,int l,int r,int pos,int val)
{
	if(pos>r || pos<l) assert(0);
	int o=newNode(maxv[prert],lson[prert],rson[prert]);
	if(l==r) {maxv[o]=val; return o;}
	else {
		int mid=(l+r)>>1;
		if(pos<=mid) lson[o]=Ins(lson[prert],l,mid,pos,val);
		else rson[o]=Ins(rson[prert],mid+1,r,pos,val);
		maxv[o]=max(maxv[lson[o]],maxv[rson[o]]);
		return o;
	}
}
int Qry(int o,int l,int r,int ql,int qr)
{
	if(ql>r || qr<l) return INT_MIN;
	if(ql<=l && r<=qr) return maxv[o];
	else {
		int mid=(l+r)>>1,ret=INT_MIN;
		if(ql<=mid) ret=max(ret,Qry(lson[o],l,mid,ql,qr));
		if(qr>mid) ret=max(ret,Qry(rson[o],mid+1,r,ql,qr));
		return ret;
	}
}
int main()
{
	freopen("longterm_segtree.in","r",stdin);
	freopen("longterm_segtree.out","w",stdout);
	n=readInt(),Q=readInt();
	for(int i=1;i<=n;i++) a[i]=readInt();
	build(rot[1],1,n);
	int ver=1,op,k,l,r;
	for(int z=0;z<Q;z++) {
		op=readInt(),k=readInt(),l=readInt(),r=readInt();
		if(op==0) {
			printf("%d\n",Qry(rot[k],1,n,l,r));
		}else {
			++ver;
			rot[ver]=Ins(rot[k],1,n,l,r);
		}
	}
	return 0;
}