题目

题目描述

     Tyvj的Admin--zhq同学将在寒假开始实行Tyvj new web计划，把Tyvj打造成为中国一流的信息学在线评测系统。Tyvj的new web计划里一共有n项，编号1~n，每项的重要度为v[i],Admin—zhq同学共工作m次，第j次从编号为l[j]~r[j]的项目里选择重要度最大的一项任务完成，所获得的进展量为(l[j]+r[j])*该任务的重要度。完成该任务后该任务的重要度变为0。请问Admin在工作m次后可以有多少进展量呢？

注：数据保证初始情况下所有任务的重要度不同。

输入

第一行为n，m 

第二行n个整数v[i]。 

接下来m行，每行两个整数l,r，表示Admin这一次将会从编号为l~r的项目里选择(包括l，r)重要度最大的来完成。 

输出

最终的进展量。由于结果可能会比较大，你只需要输出mod2011之后的结果即可。

输入样例复制

5 3 1 2 3 4 5 1 3 2 3 1 5

输出样例复制

52

说明

对于50%的数据，1<=n,m<=1000 

对于100%的数据，1<=n,m<=200000,1<=L<=r<=n,1<=v[i]<=100000 

 

分析

•      一个线段树+单点修改+区间查询

代码

1 #include
     
       2 #include
      
        3 #define ll long long 4 using namespace std; 5 struct sb 6 { 7     ll l,r,num,id; 8 }t[1000001]; 9 ll n,m;10 ll maxx,wz;11 inline long long read()12 {13     char c;int d=1;long long f=0;14     while(c=getchar(),!isdigit(c))if(c==45)d=-1;f=(f<<3)+(f<<1)+c-48;15     while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;16     return d*f;17 }18 void up(ll k)    //比较区间最大值19 {20     if (t[k*2].num>t[k*2+1].num)21     {22         t[k].num=t[k*2].num;23         t[k].id=t[k*2].id;24     }25     else26     {27         t[k].num=t[k*2+1].num;28         t[k].id=t[k*2+1].id;29     }30     return;31 }32 void build(ll a,ll b,ll k)  //建树33 {34     t[k].l=a; t[k].r=b;35     if (a==b)36     {37         t[k].num=read();38         t[k].id=t[k].l;39         return;40     }41     ll mid=(a+b)/2;42     build(a,mid,2*k);43     build(mid+1,b,2*k+1);44     up(k);45 }46 void find(ll a,ll b,ll k)    //查找47 {48     if (t[k].l==a&&t[k].r==b)49     {50         if (t[k].num>maxx)51         {52             maxx=t[k].num;53             wz=t[k].id;54         }55         return;56     }57     ll mid=(t[k].l+t[k].r)/2;58     if (b<=mid) find(a,b,k*2);59     else if (a>mid) find(a,b,k*2+1);60     else {61         find(a,mid,k*2);62         find(mid+1,b,k*2+1);63     }64 }65 void change(ll wz,ll k)  //修改值66 {67     if (t[k].l==t[k].r)68     {69         t[k].num=0;70         t[k].id=0;71         return;72     }73     ll mid=(t[k].l+t[k].r)/2;74     if (mid>=wz) change(wz,k*2);75     else if (mid
       
        >n>>m;81     build(1,n,1);82     ll ans=0;83     for (ll i=1,x,y;i<=m;i++)84     {85         x=read();86         y=read();87         maxx=0;wz;88         find(x,y,1);89         change(wz,1);90         ans+=(x+y)*maxx;91         ans%=2011;92     }93     cout<