【BZOJ2006】超级钢琴（主席树，优先队列）

题面

BZOJ

题解

既然是一段区间

首先就要变成单点

所以求一个前缀和

这个时候贪心很明显了：

枚举每一个点和可以和它组成一段的可行的点

全部丢进一个堆里面

取出最大的\(K\)个就行了

但是，很显然，我们做不到都取出来

所以，考虑怎么优化这个过程

每次堆里面对于每个点就先维护一个最大贡献

显然的，只有取出了最大贡献，才会取出次大贡献

那么，最大/次大/\(K\)大贡献怎么算？

一个点，能够和他组成和弦的是一个连续的区间

最大的贡献就是它和区间最小值的差

依次类推

就是区间第\(K\)大

所以搞一棵主席树

维护一下区间第\(K\)大就好啦

再用堆每次取出/加入即可

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define MAX 510000

inline int read()

{

	int x=0,t=1;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=-1,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return x*t;

}

struct Data{int v,id,k;};

bool operator<(Data a,Data b){return a.v<b.v;}

priority_queue<Data> Q;

struct Node

{

	int ls,rs;

	int sum;

}t[MAX<<6];

int tot,S[MAX],top,rt[MAX],L,R,n,K;

int a[MAX];

void Modify(int &now,int ff,int l,int r,int pos,int w)

{

	t[now=++tot]=t[ff];t[now].sum+=w;

	if(l==r)return;

	int mid=(l+r)>>1;

	if(pos<=mid)Modify(t[now].ls,t[ff].ls,l,mid,pos,w);

	else Modify(t[now].rs,t[ff].rs,mid+1,r,pos,w);

}

int Query(int A,int B,int l,int r,int K)

{

	if(l==r)return l;

	int mid=(l+r)>>1;

	int sum=t[t[A].ls].sum-t[t[B].ls].sum;

	if(sum<K)return Query(t[A].rs,t[B].rs,mid+1,r,K-sum);

	else return Query(t[A].ls,t[B].ls,l,mid,K);

}

int main()

{

	n=read()+1;K=read();L=read();R=read();

	for(int i=2;i<=n;++i)S[++top]=a[i]=a[i-1]+read();S[++top]=0;

	sort(&S[1],&S[top+1]);

	top=unique(&S[1],&S[top+1])-S-1;

	for(int i=1;i<=n;++i)a[i]=lower_bound(&S[1],&S[top+1],a[i])-S;

	for(int i=1;i<=n;++i)Modify(rt[i],rt[i-1],1,top,a[i],1);

	for(int i=L+1;i<=n;++i)

	{

		Data x;x.id=i;x.k=1;

		x.v=S[a[i]]-S[Query(rt[i-L],rt[max(0,i-R-1)],1,top,1)];

		Q.push(x);

	}

	long long ans=0;

	while(K--)

	{

		Data x=Q.top();Q.pop();

		ans+=x.v;

		if(x.k==min(x.id-L,R-L+1))continue;

		x.k++;

		x.v=S[a[x.id]]-S[Query(rt[x.id-L],rt[max(0,x.id-R-1)],1,top,x.k)];

		Q.push(x);

	}

	printf("%lld\n",ans);

	return 0;

}