[NOI2010]超級鋼琴

鏈接

luogu

思路

和12省聯考的異或粽子一樣。
堆維護n個左端點，每次取出來再放回去次

代碼

#include <bits/stdc++.h> #define ll long long using namespace std; const int _=5e5+7,INF=0x3f3f3f3f; int read() {int x=0,f=1;char s=getchar();for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';return x*f; } int n,k,l,r,sum[_],rt[_]; namespace seg {struct node {int l,r,siz;}e[_*20];int cnt;void insert(int l,int r,int k,int x,int &y) {e[y=++cnt]=e[x];e[y].siz++;if(l==r) return;int mid=(l+r)>>1;if(k<=mid) insert(l,mid,k,e[x].l,e[y].l);else insert(mid+1,r,k,e[x].r,e[y].r);}int query(int l,int r,int k,int x,int y) {if(l==r) return l;int mid=(l+r)>>1,h=e[e[y].l].siz-e[e[x].l].siz;if(k<=h) return query(l,mid,k,e[x].l,e[y].l);else return query(mid+1,r,k-h,e[x].r,e[y].r);} } struct node {int val,l,r,k,id;bool operator < (const node &b) const {return val<b.val;} }; priority_queue<node> q; int lsh[_]; int main() {n=read(),k=read(),l=read(),r=read();for(int i=1;i<=n;++i) lsh[i]=sum[i]=sum[i-1]+read(); sort(lsh+1,lsh+1+n);int len=unique(lsh+1,lsh+1+n)-lsh-1;for(int i=1;i<=n;++i) sum[i]=lower_bound(lsh+1,lsh+1+len,sum[i])-lsh;for(int i=1;i<=n;++i) seg::insert(1,n,sum[i],rt[i-1],rt[i]);for(int i=0;i<=n-l;++i) {int L=i+l,R=min(i+r,n);q.push(node{lsh[seg::query(1,n,R-L+1,rt[L-1],rt[R])]-lsh[sum[i]],L,R,R-L+1,i});}ll ans=0;while(k --> 0) {node u=q.top();q.pop();ans+=u.val;u.k--;if(u.k<=0) continue;u.val=lsh[seg::query(1,n,u.k,rt[u.l-1],rt[u.r])]-lsh[sum[u.id]];q.push(u);}cout<<ans<<"\n";return 0; }

轉載于:https://www.cnblogs.com/dsrdsr/p/11405964.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[NOI2010]超级钢琴 主席树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。