首页 > 代码库 > COGS 827. [Tyvj Feb11] 网站计划
COGS 827. [Tyvj Feb11] 网站计划
输入文件：web.in 输出文件：web.out 简单对比
时间限制：1 s 内存限制：128 MB
| 描述 Description | ||
| 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次后可以有多少进展量呢？ 注：数据保证初始情况下所有任务的重要度不同。 | ||
输入格式 Input Format
第一行为n，m
第二行n个整数v[i]。
接下来m行，每行两个整数l,r，表示Admin这一次将会从编号为l~r的项目里选择(包括l，r)重要度最大的来完成。
输出格式 Output Format | ||
| 最终的进展量。由于结果可能会比较大，你只需要输出mod2011之后的结果即可。 | ||
输出格式 Output Format | ||
| 最终的进展量。由于结果可能会比较大，你只需要输出mod2011之后的结果即可。 | ||
样例输入：
5 3
1 2 3 4 5
1 3
2 3
1 5
样例输出：
52
线段树
区间最大值 单点修改
屠龙宝刀点击就送
#include <iostream>#include <cstdio>using namespace std;typedef long long LL;struct node{ LL l,r,dis,v;}t[200000*4+1];LL whr,to,maxn,n,m;void up(LL k){ if(t[k<<1].dis>t[k<<1|1].dis) { t[k].dis=t[k<<1].dis; t[k].v=t[k<<1].v; } else { t[k].dis=t[k<<1|1].dis; t[k].v=t[k<<1|1].v; }}void build(LL l,LL r,LL k){ t[k].l=l;t[k].r=r; if(l==r) { scanf("%d",&t[k].dis); t[k].v=t[k].l; return; } LL mid=(l+r)>>1; build(l,mid,k<<1); build(mid+1,r,k<<1|1); up(k);}void query(LL l,LL r,LL k){ if(t[k].l==l&&t[k].r==r) { if(t[k].dis>maxn) { maxn=t[k].dis; whr=t[k].v; } return; } LL mid=(t[k].l+t[k].r)>>1; if(r<=mid) query(l,r,k<<1); else if(l>mid) query(l,r,k<<1|1); else { query(l,mid,k<<1); query(mid+1,r,k<<1|1); }}void delet(LL now,LL k){ if(t[k].l==t[k].r) { t[k].dis=0; t[k].v=0; return; } LL mid=(t[k].l+t[k].r)>>1; if(mid>=now) delet(now,k<<1); else if(mid<now) delet(now,k<<1|1); up(k);}int main(){ freopen("web.in","r",stdin); freopen("web.out","w",stdout); cin>>n>>m; build(1,n,1); LL u,v; long long ans=0; while(m--) { cin>>u>>v; maxn=0;whr; query(u,v,1); delet(whr,1); ans+=(u+v)*maxn%2011; ans%=2011; } cout<<ans; return 0;}
COGS 827. [Tyvj Feb11] 网站计划
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。