[NOI2010bzoj2006]超级钢琴

题目大意

给定n个数的序列，求长度在L,R之间的连续子序列中，区间和前k大的和。

n,k≤500000，-1000≤ai≤1000

分析

首先求出前缀和，那么区间和变成两个数的差。 假设当前要求第i大，对于每个区间的l，都有一个数now[l]，表示对于这个l，在对应长度范围内（即区间[l,r]长度在给定范围内），前now[l]-1大的区间和已经是前i-1大的区间和。然后对于每个l的第now[l]大的区间和，把它们放进一个堆里面，然后每次取出最大值，把对应l的now加1，再把现在的第now[l]大的数放进堆里。 所以还需要一个数据结构查询静态区间第k大。

时间复杂度 O(nlogn)

代码

#include <cstdio> #include <cstring> #include <algorithm> #define fi first #define se second using namespace std; const int maxn=500005,maxm=20000005,N=500000000; typedef long long LL; typedef pair<int,int> PII; int n,m,l,r,root[maxn],left[maxm],right[maxm],sum[maxm],tot,now[maxn],a[maxn],pre[maxn],cnt[maxn]; LL ans; PII heap[maxn]; void insert(int l,int r,int g,int &x,int y) { x=++tot; sum[x]=sum[y]+1; if (l==r) return; left[x]=left[y]; right[x]=right[y]; int mid=l+r>>1; if (g<=mid) insert(l,mid,g,left[x],left[y]);else insert(mid+1,r,g,right[x],right[y]); } int get(int l,int r,int rank,int x,int y) { if (l==r) return l; int mid=l+r>>1; if (sum[right[x]]-sum[right[y]]>=rank) return get(mid+1,r,rank,right[x],right[y]); return get(l,mid,rank-sum[right[x]]+sum[right[y]],left[x],left[y]); } void up(int x) { for (;x>1 && heap[x>>1].fi<heap[x].fi;x/=2) { heap[0]=heap[x>>1]; heap[x>>1]=heap[x]; heap[x]=heap[0]; } } void down() { int i,son; for (i=1;i+i<=tot;i=son) { son=(i+i==tot || heap[i<<1].fi>heap[(i<<1)+1].fi)?i<<1:(i<<1)+1; if (heap[i].fi>heap[son].fi) break; heap[0]=heap[i]; heap[i]=heap[son]; heap[son]=heap[0]; } } int main() { scanf("%d%d%d%d",&n,&m,&l,&r); for (int i=1;i<=n;i++) { scanf("%d",&a[i]); pre[i]=pre[i-1]+a[i]; insert(0,N+N,pre[i]+N,root[i],root[i-1]); } tot=0; for (int i=1;i+l-1<=n;i++) { now[i]=1; cnt[i]=min(r-l+1,n-i-l+2); heap[++tot].fi=get(0,N+N,1,root[i+l+cnt[i]-2],root[i+l-2])-N-pre[i-1]; heap[tot].se=i; up(tot); } ans=0; while (m--) { ans+=heap[1].fi; int x=heap[1].se; heap[1]=heap[tot--]; down(); now[x]++; if (now[x]>cnt[x]) continue; heap[++tot].fi=get(0,N+N,now[x],root[x+l+cnt[x]-2],root[x+l-2])-N-pre[x-1]; heap[tot].se=x; up(tot); } printf("%lld\n",ans); return 0; }