记录编号	309591	评测结果	AAAAAAAAA
题目名称	[Tyvj Feb11] 网站计划	最终得分	100
用户昵称	沉迷学习的假的Keller	是否通过	通过
代码语言	C++	运行时间	1.956 s
提交时间	2016-09-20 09:23:22	内存使用	9.50 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
#define lint long long
using namespace std;
const int maxn=200000+10;
lint n,m;
lint v[maxn],l[maxn],r[maxn];
struct node{
	lint mx,pos;
}maxx[4*maxn];

void pushup(int id){
	if(maxx[id*2].mx>maxx[id*2+1].mx){
		maxx[id].mx=maxx[id*2].mx;
		maxx[id].pos=maxx[id*2].pos;
	}
	else {
		maxx[id].mx=maxx[id*2+1].mx;
		maxx[id].pos=maxx[id*2+1].pos;	
	}
}
void build(int l,int r,int id){
	if(l==r) {
		maxx[id].mx=v[l];
		maxx[id].pos=l;
		return ;
	}
	int mid=(l+r)/2;
	build(l,mid,id*2);
	build(mid+1,r,id*2+1);
	pushup(id);
}

node query(int l,int r,int id,int x,int y){
	if(x<=l&&r<=y){
		return maxx[id];
	}
	int mid=(l+r)/2;
	int q=-1;
	int poss;
	if(x<=mid){
		node p=query(l,mid,id*2,x,y);
		if(p.mx>q){
			q=p.mx;
			poss=p.pos;
		}
	}
	if(y>mid){
		node p=query(mid+1,r,id*2+1,x,y);
		if(p.mx>q){
			q=p.mx;
			poss=p.pos;	
		}
	}
	node re={q,poss};
	return re;
}

void update(int l,int r,int id,int k,int val){
	if(l==r){
		maxx[id].mx=val;
		return;
	}
	int mid=(l+r)/2;
	if(k<=mid){
		update(l,mid,id*2,k,val);
	}
	else {
		update(mid+1,r,id*2+1,k,val);	
	}
	pushup(id);
}

int MAIN(){
	freopen("web.in","r",stdin);
	freopen("web.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&v[i]);
	}
	build(1,n,1);
	lint ans=0;
	for(int i=1;i<=m;i++){
		scanf("%lld%lld",&l[i],&r[i]);
		node b=query(1,n,1,l[i],r[i]);
		ans+=((l[i]+r[i])*b.mx)%2011;
		ans%=2011;
		//printf("%d\n",ans);
		update(1,n,1,b.pos,0);
	}
	printf("%lld",ans);
	return 0;
}
int main(){;}
int helenkeller=MAIN();