记录编号	568803	评测结果	AAAAAAAAAA
题目名称	可持久化线段树	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	0.232 s
提交时间	2022-02-02 10:13:38	内存使用	0.00 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
inline int read(){
	int sum(0);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
int n,q,t(1);
int a[10005];
int cnt;
int rt[100005],lch[20000005],rch[20000005],mx[20000005];
inline void pushup(int i){
	mx[i]=max(mx[lch[i]],mx[rch[i]]);
}
inline void build(int &x,int l,int r){
	x=++cnt;
	if(l==r){
		mx[x]=a[l];
		return;
	}
	int mid((l+r)>>1);
	build(lch[x],l,mid);
	build(rch[x],mid+1,r);
	pushup(x);
}
inline void update(int &x,int las,int pos,int w,int l,int r){
	x=++cnt;
	lch[x]=lch[las];
	rch[x]=rch[las];
	mx[x]=mx[las];
	if(l==r){
		mx[x]=w;
		return;
	}
	int mid((l+r)>>1);
	if(pos<=mid)
		update(lch[x],lch[las],pos,w,l,mid);
	else
		update(rch[x],rch[las],pos,w,mid+1,r);
	pushup(x);
}
inline int query(int x,int ll,int rr,int l,int r){
	if(ll<=l&&r<=rr)
		return mx[x];
	int mid((l+r)>>1);
	if(rr<=mid)
		return query(lch[x],ll,rr,l,mid);
	if(mid<ll)
		return query(rch[x],ll,rr,mid+1,r);
	return max(query(lch[x],ll,mid,l,mid),query(rch[x],mid+1,rr,mid+1,r));
}
inline int gg(){
	freopen("longterm_segtree.in","r",stdin);
	freopen("longterm_segtree.out","w",stdout);
	n=read(),q=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	build(rt[1],1,n);
	while(q--){
		int op(read()),x(read()),y(read()),z(read());
		if(op==0)
			printf("%d\n",query(rt[x],y,z,1,n));
		else
			update(rt[++t],rt[x],y,z,1,n);
	}
	return 0;
}
int K(gg());
int main(){;}