[luogu2048] [bzoj2006] [NOI2010] 超级钢琴 题…
2018-06-17 21:18:00来源:未知 阅读 ()
花了一个星期,总算把这一道该死的毒瘤题做完了。
这道题有很多种解法,我是用优先队列+主席树。
首先每一个区间的和,可以表示为两个前缀和之差。
我们显然可以知道,每一次找到的那个最大值必然在以一个点为最后一个点的区间之内。
所以我们可以把每一个点为最后一个点的最大值的区间求出来,先打入队列。
然后每一次打出来一个值,我们就把这个区间的最后一个值的位置的排名前一名的那一个区间打入队列。
这样重复计算即可。
至于实现,我们可以将每一个前缀和建一个主席树,然后我们维护一个三元组(add,cnt,end)
add维护区间和。
cnt维护当前在以这个最后一个位置最后的区间的排名。
end维护结尾的点。
具体实现有点迷,注意在建主席树的时候记得把0给建进去,会少不少麻烦。
剩下的就是主席树区间第k大了。
贴上代码:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<queue> #define maxn 500100 using namespace std; typedef long long ll; ll a[maxn]; ll b[maxn]; int lx,rx,n,k; int root[maxn]; int tot; struct P{ int l,r,sum; }tree[maxn*20]; struct X{ ll add; int cnt,end; }; map<ll,int>ma; struct cmp{ bool operator () (const X a,const X b) const { return a.add<b.add; } }; priority_queue<X,vector<X>,cmp > q; void update(int k1,int k2,int l,int r,int x)//k1-build,k2-find { if(l==r) { tree[k1].sum=tree[k2].sum+1; return; } else { int mid=(l+r)/2; if(x>=l&&x<=mid) { tot++; tree[k1].l=tot; tree[k1].r=tree[k2].r; update(tree[k1].l,tree[k2].l,l,mid,x); } else { tot++; tree[k1].r=tot; tree[k1].l=tree[k2].l; update(tree[k1].r,tree[k2].r,mid+1,r,x); } } tree[k1].sum=tree[tree[k1].l].sum+tree[tree[k1].r].sum; } int query(int i,int j,int k,int l,int r) { if(l==r) return l; int t=tree[tree[j].l].sum-tree[tree[i].l].sum; int mid=(l+r)/2; if(k<=t) return query(tree[i].l,tree[j].l,k,l,mid); else return query(tree[i].r,tree[j].r,k-t,mid+1,r); } void work(int a,int b,int c) { X y; y.add=a; y.end=b; y.cnt=c; q.push(y); } ll ans; int main() { scanf("%d%d%d%d",&n,&k,&lx,&rx); for(int i=1;i<=n;i++) { ll x; scanf("%lld",&x); a[i+1]=a[i]+x; } for(int i=1;i<=n+1;i++) b[i]=a[i]; sort(b+1,b+n+2); int o=unique(b+1,b+n+2)-b-1; for(int i=1;i<=o;i++) ma[b[i]]=i; for(int i=1;i<=n+1;i++) root[i]=i; tot=n+1; for(int i=1;i<=n+1;i++) update(root[i],root[i-1],1,o,ma[a[i]]); for(int i=lx;i<=n;i++) { int p1=i-lx+1; int p2=max(1,i-rx+1); ll t=b[query(root[p2-1],root[p1],1,1,o)]; work(a[i+1]-t,i,1); } int sumx=0; while(true) { X now=q.top(); q.pop(); ans+=now.add; sumx++; if(sumx==k) break; int p1=now.end; int p2=now.cnt; int k1=p1-lx+1; int k2=max(p1-rx+1,1); if(p2==k1-k2+1) continue; else{ ll u=b[query(root[k2-1],root[k1],p2+1,1,o)]; work(a[p1+1]-u,p1,p2+1); } } cout<<ans<<endl; return 0; } /* 4 3 2 3 3 2 -6 8 */
有什么写的不好的地方大家尽管提出。
谢谢!!
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- P3205 [HNOI2010]合唱队 2019-08-26
- BZOJ2005: [Noi2010]能量采集(容斥原理 莫比乌斯反演) 2018-07-09
- NOI2010 超级钢琴 2018-06-27
- bzoj2006 [ NOI2010 ] && bzoj3784 --点分 2018-06-17
- bzoj2002 [ HNOI2010 ] -- LCT 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash