记录编号	469890	评测结果	AAAAAAAAAA
题目名称	可持久化线段树	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	0.213 s
提交时间	2017-11-03 21:30:25	内存使用	15.58 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
const int maxn=10010;
int n,m;
int gen[1000010],sz;
int maxx[maxn*100],ls[maxn*100],rs[maxn*100];
inline void change(int shang,int &xin,int l,int r,int nl,int nr,int v){
	xin=++sz;
	if(l>=nl&&r<=nr){
		maxx[xin]=v;
		return ;
	}
	int m=(l+r)>>1;
	ls[xin]=ls[shang];
	rs[xin]=rs[shang];
	if(m>=nl)change(ls[shang],ls[xin],l,m,nl,nr,v);
	if(m<nr)change(rs[shang],rs[xin],m+1,r,nl,nr,v);
	maxx[xin]=max(maxx[ls[xin]],maxx[rs[xin]]);
}
inline int find(int xin,int l,int r,int nl,int nr){
	if(l>=nl&&r<=nr){return maxx[xin];}
	int ans=-0x7fffffff;
	int m=(l+r)>>1;
	if(m>=nl)ans=max(ans,find(ls[xin],l,m,nl,nr));
	if(m<nr)ans=max(ans,find(rs[xin],m+1,r,nl,nr));
	return ans;
}
int main(){
	freopen("longterm_segtree.in","r",stdin);
	freopen("longterm_segtree.out","w",stdout);
	n=read();m=read();
	int k=1;
	for(int i=1;i<=n;i++){
		int x=read();
		change(gen[k],gen[k],1,n,i,i,x);
	}
	for(int i=1;i<=m;i++){
		int c=read(),ban=read(),x=read(),y=read();
		if(c==0){
			printf("%d\n",find(gen[ban],1,n,x,y));
		} 
		if(c==1){
			change(gen[ban],gen[++k],1,n,x,x,y);
		}
	}
	return 0;
}