记录编号	155656	评测结果	AAAAAAAAAA
题目名称	区间权最大	最终得分	100
用户昵称	new ioer	是否通过	通过
代码语言	C++	运行时间	1.612 s
提交时间	2015-03-29 18:46:03	内存使用	7.92 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=200010;
struct ask{
	int l,r,x,id;
}q[maxn];
struct node{
	node *c[2];
	int v,siz,maxm;
	node *init();
	void mata(){
		siz=c[0]->siz+c[1]->siz+1;
		maxm=max(v,max(c[0]->maxm,c[1]->maxm));
	}
	int cmp(int k){
		if(k<=c[0]->siz) return 0;
		if(k==c[0]->siz+1) return -1;
		return 1;
	}
}Null,spt[maxn],*root;
node *node::init(){
	v=maxm=0,siz=1,c[0]=c[1]=&Null;
	return this;
}
int n,m,tot,cnt,maxr,ans[maxn];
bool cmp(ask a,ask b){
	if(a.r!=b.r) return a.r<b.r;
	return a.id<b.id;
}
node *build(int l,int r){
	if(l==r) return spt[++cnt].init();
	int mid=(l+r)>>1;
	node *tmp=spt[++cnt].init();
	if(l<mid) tmp->c[0]=build(l,mid-1);
	if(r>mid) tmp->c[1]=build(mid+1,r);
	tmp->mata();
	return tmp;
}
void rot(node *&o,bool k){
	node *tmp=o->c[k];
	o->c[k]=tmp->c[!k];
	tmp->c[!k]=o;
	o->mata(),tmp->mata(),o=tmp;
}
void splay(node *&o,int k){
	int k1=o->cmp(k);
	if(k1==-1) return;
	if(k1) k-=o->c[0]->siz+1;
	int k2=o->c[k1]->cmp(k);
	if(~k2){
		if(k2) k-=o->c[k1]->c[0]->siz+1;
		splay(o->c[k1]->c[k2],k);
		if(k1==k2) rot(o,k1);
		else rot(o->c[k1],k2);
	} 
	rot(o,k1);
}
int query(int l,int r){
	l++,r++;
	int len=r-l+1;
	splay(root,l-1),splay(root->c[1],len+1);
	return root->c[1]->c[0]->maxm;
}
void change(int i,int x){
	splay(root,++i);
	root->v=max(root->v,x);
	root->maxm=max(root->maxm,root->v);
}
int main(){
	freopen("max.in","r",stdin);
	freopen("max.out","w",stdout);
	scanf("%d%d",&n,&m),tot=m+n;
	for(int i=1;i<=n;i++) scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].x),maxr=max(maxr,q[i].r);
	for(int i=1,j=n+1;i<=m;i++,j++) scanf("%d%d",&q[j].l,&q[j].r),maxr=max(maxr,q[j].r),q[j].id=i;
	root=build(0,maxr+1);
	sort(q+1,q+tot+1,cmp);
	for(int i=1;i<=tot;i++){
		if(q[i].id) ans[q[i].id]=query(q[i].l,q[i].r);
		else change(q[i].l,q[i].x);
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
}