记录编号	155261	评测结果	AAAAAAAAAA
题目名称	区间权最大	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.919 s
提交时间	2015-03-28 07:29:07	内存使用	10.23 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,i,zj1,zj2,zj3,N;
struct www{
	int typ,l,r,w;
	bool operator <(const www&b)const
	{return (r<b.r)||(r==b.r&&typ<b.typ);}
}B[200010];
int ret[100010]={0},ans[100010]={0},ANS;

struct wwww{int fa,L,R,Max;} A[400000];
inline void make(int now)
{
	if(A[now].L==A[now].R)
	{
		ret[A[now].L]=now;
		return;
	}
	int mid=(A[now].L+A[now].R)>>1;
	A[now<<1].L=A[now].L,A[now<<1].R=mid;
	A[(now<<1)+1].L=mid+1,A[(now<<1)+1].R=A[now].R;
	make(now<<1);make((now<<1)+1);
}
inline void Findmax(int x,int ll,int rr)
{
	if((ll<=A[x].L)&&(rr>=A[x].R))
	{if(ANS<A[x].Max)ANS=A[x].Max;return;}
	int mid=(A[x].L+A[x].R)>>1;if(mid>=ll&&mid<rr)
	{Findmax(x<<1,ll,mid);Findmax((x<<1)+1,mid+1,rr);}
	else if(mid<ll)Findmax((x<<1)+1,ll,rr);
	else Findmax(x<<1,ll,rr);
}
int main()
{
	freopen("max.in","r",stdin);
	freopen("max.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		B[i].typ=1;
		scanf("%d%d%d",&B[i].l,&B[i].r,&B[i].w);
		if(B[i].l>N)N=B[i].l;
	}
	for(i=1;i<=m;i++)
	{
		B[i+n].typ=2;B[i+n].w=i;
		scanf("%d%d",&B[i+n].l,&B[i+n].r);
		if(B[i+n].l>N)N=B[i+n].l;
	}
	sort(B+1,B+(n+m+1));
	A[1].L=1,A[1].R=N;
	make(1);
	zj1=1;
	for(n+=m,i=1;i<=n;i++)
	{
		if(B[i].typ==1)
		{
			zj1=ret[B[i].l];
			A[zj1].Max=max(A[zj1].Max,B[i].w);
			zj1>>=1;
			while(zj1)
			{
				A[zj1].Max=A[zj1<<1].Max;
				if(A[zj1].Max<A[(zj1<<1)+1].Max)
				A[zj1].Max=A[(zj1<<1)+1].Max;
				zj1>>=1;
			}
		}
		else
		{
			ANS=0;
			Findmax(1,B[i].l,n);
			ans[B[i].w]=ANS;
		}
	}
	for(i=1;i<=m;i++)printf("%d\n",ans[i]);
	return 0;
}