记录编号	444117	评测结果	AAAAAAAAA
题目名称	[Tyvj Feb11] 网站计划	最终得分	100
用户昵称	+1s	是否通过	通过
代码语言	C++	运行时间	1.020 s
提交时间	2017-09-02 09:24:11	内存使用	41.39 MiB

#include<cstdio>
#include<cmath>
using namespace std;
int n,m,v[200020];
struct{long long l,r,mx,pnt;}stree[2000020];
void bui(int l,int r,int idx)
{
	stree[idx].l=l;
	stree[idx].r=r;
	if(stree[idx].l==stree[idx].r)
	{
		stree[idx].mx=v[l];
		stree[idx].pnt=l;
		return;
	}
	int m=(l+r)/2;
	bui(l,m,idx*2);
	bui(m+1,r,idx*2+1);
	if(stree[idx*2].mx>stree[idx*2+1].mx)
	{
		stree[idx].pnt=stree[idx*2].pnt;
		stree[idx].mx=stree[idx*2].mx;
	}
	else
	{
		stree[idx].pnt=stree[idx*2+1].pnt;
		stree[idx].mx=stree[idx*2+1].mx;
	}
}
void upda(int de,int idx)
{
	if(stree[idx].l>de||de>stree[idx].r)return;
	if(stree[idx].l==stree[idx].r&&de==stree[idx].l)
	{
		stree[idx].mx=0;
		return;
	}
	upda(de,idx*2);
	upda(de,idx*2+1);
	if(stree[idx*2].mx>stree[idx*2+1].mx)
	{
		stree[idx].mx=stree[idx*2].mx;
		stree[idx].pnt=stree[idx*2].pnt;
	}
	else
	{
		stree[idx].mx=stree[idx*2+1].mx;
		stree[idx].pnt=stree[idx*2+1].pnt;
	}
}
int qry(int l,int r,int idx,int *p)
{
	if(stree[idx].l==0&&stree[idx].r==0)return 0;
	if(stree[idx].l==l&&stree[idx].r==r)
	{
		*p=stree[idx].pnt;
		return stree[idx].mx;
	}
	if(r<=stree[idx*2].r)return qry(l,r,idx*2,p);
	if(l>=stree[idx*2+1].l)return qry(l,r,idx*2+1,p);
	int ap,bp;
	int a=qry(l,stree[idx*2].r,idx*2,&ap);
	int b=qry(stree[idx*2+1].l,r,idx*2+1,&bp);
	if(a>b)
	{
		*p=ap;
		return a;
	}
	else
	{
		*p=bp;
		return b;
	}
}
int faq()
{
	freopen("web.in","r",stdin);
	freopen("web.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&v[i]);
	bui(1,n,1);
	int l,r,tp;
	long long re=0;
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d",&l,&r);
		long long mv=qry(l,r,1,&tp);
		upda(tp,1);
		re=(re+(((l%2011+r%2011)%2011)*(mv%2011))%2011)%2011;
	}
	printf("%d",re);
}
int mn=faq();
int main()
{
	return 0;
}