记录编号	410859	评测结果	AAAAAAAAAA
题目名称	可持久化线段树	最终得分	100
用户昵称	rvalue	是否通过	通过
代码语言	C++	运行时间	0.303 s
提交时间	2017-06-02 20:32:46	内存使用	0.70 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN=100100;
const int INF=0x7FFFFFFF;

struct Node{
	int max;
	int l;
	int r;
	Node* lch;
	Node* rch;
};
Node* N[MAXN];

int n;
int q;
int cnt;

void Build(Node*,int,int);
Node* Change(Node*,const int&,const int&);
int Query(Node*,const int&,const int&);
void FastRead(int&);

int main(){
	freopen("longterm_segtree.in","r",stdin);
	freopen("longterm_segtree.out","w",stdout);

	int a,b,c,d;
	FastRead(n);
	FastRead(q);
	Build(N[1]=new Node,1,n);
	cnt=1;
	for(int i=0;i<q;i++){
		FastRead(a);
		FastRead(b);
		FastRead(c);
		FastRead(d);
		if(a){
			N[++cnt]=Change(N[b],c,d);
		}
		else{
			printf("%d\n",Query(N[b],c,d));
		}
	}
	return 0;
}

void Build(Node* root,int l,int r){
	root->l=l;
	root->r=r;
	if(l==r){
		FastRead(root->max);
	}
	else{
		int mid=(l+r)>>1;
		Build(root->lch=new Node,l,mid);
		Build(root->rch=new Node,mid+1,r);
		root->max=max(root->lch->max,root->rch->max);
	}
}

int Query(Node* root,const int& l,const int& r){
	if(l<=root->l&&root->r<=r){
		return root->max;
	}
	else{
		int ans=-INF;
		if(l<=root->lch->r)
			ans=max(ans,Query(root->lch,l,r));
		if(root->rch->l<=r)
			ans=max(ans,Query(root->rch,l,r));
		return ans;
	}
}

Node* Change(Node* root,const int& x,const int& d){
	Node* tmp=new Node;
	tmp->l=root->l;
	tmp->r=root->r;
	if(root->l==root->r){
		tmp->max=d;
	}
	else{
		if(x<=root->lch->r){
			tmp->lch=Change(root->lch,x,d);
			tmp->rch=root->rch;
		}
		else{
			tmp->rch=Change(root->rch,x,d);
			tmp->lch=root->lch;
		}
		tmp->max=max(tmp->lch->max,tmp->rch->max);
		// printf("[LOG]l:%d r:%d max:%d lmax:%d rmax:%d xmax:%d\n",tmp->l,tmp->r,tmp->max,tmp->lch->max,tmp->rch->max,max(tmp->rch->max,tmp->rch->max));
	}
	return tmp;
}

inline void FastRead(int& target){
	target=0;
	register char ch=getchar();
	while(ch>'9'||ch<'0')
		ch=getchar();
	while(ch<='9'&&ch>='0'){
		target=target*10+ch-'0';
		ch=getchar();
	}
}