题解 P2048 [NOI2010]超级钢琴。

题面

有一数列，包含 $n$ 个数，编号为 $1$ 至 $n$ 。第 $i$ 个数权值为 $A_i$ 。

我们要找到 $k$ 段连续子序列，满足其中数的数量 $x$ 保证 $L\leq x\leq R$ ，求这 $k$ 段序列中所有数字的权值和的最大值。

所有数据满足： $-1000 \leq A_i \leq 1000$ ， $1 \leq L \leq R \leq n$ ， $1 \le n,k \le 500000$ ，且保证一定有解。

题解

可以想到，求区间和用前缀和。使用贪心思想来解决这个问题。

设 $f_i(l,r)$ 表示以 $i$ 为左端点，右端点在 $[l,r]$ 区间中，序列的最大值。设 $s(i)$ 是前缀和。

则 $f_i(l,r)=s(x_i)-s(i-1)$ 。其中 $x_i \in [l,r]$ ，使 $f_i(l,r)$ 最大。

那么就要求 $x_i$ 。由于 $s(i-1)$ 值固定，也就是求 $s(x_i)$ ，也就是求区间最大值（前缀和数组），可以用 st 表解决。

求得对于所有 $i\in[1,n]$ ，满足使 $f_i(l,r)$ 的值最大的 $x_i$ 后，把这些相关值（ $i$ ， $l$ ， $r$ ， $x _i$ ， $f_i(l,r)$ ）搞成结构体，放入一个堆中。

循环 $k$ 次，每次取最大的 $f_i(l,r)$ ，把 $f_i(l,r)$ 累加起来。

取完后，可能还有次优 $x$ 值存在于 $[l,r]$ 。故也要求使 $f_i(l,x_i-1)$ 和 $f_i(x_i+1,r)$ 的值最大的对应 $x$ 值，把求解过程中的相关值也放入堆（即在区间 $[l, r]$ 排除了 $x_i $）。

累加起来的值即为答案。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	const int N=600000+5,log=19;
	struct music{int s,l,r,a;};//采用四元组，表示i,l,r,xi。fi(l,r) 现场求即可。
	int n,k,L,R,b[N],st[25][N];
	long long ans=0,a[N];
	priority_queue<music>q;
	bool operator<(music x,music y){return a[x.a]-a[x.s-1]<a[y.a]-a[y.s-1];}
	int query(int l,int r)
	{
		int len=r-l+1;
		if(a[st[b[len]][l]]>a[st[b[len]][r+1-(1<<b[len])]])
			return st[b[len]][l];
		return st[b[len]][r+1-(1<<b[len])];
	}
	void yzmain()
	{
		scanf("%d%d%d%d",&n,&k,&L,&R);
		for(int i=1;i<=n;i++) scanf("%lld",a+i),a[i]+=a[i-1];
		for(int i=1;i<=n;i++) st[0][i]=i;//st 表存的是 xi
		for(int i=1;i<=log;i++) b[1<<i]=1;
		for(int i=1;i<=n;i++) b[i]+=b[i-1];
		for(int i=1;i<=log;i++)
			for(int j=1;j<=n;j++)
				if(a[st[i-1][j]]>a[st[i-1][j+(1<<(i-1))]])
					st[i][j]=st[i-1][j];
				else
					st[i][j]=st[i-1][j+(1<<(i-1))];
		for(int i=1;i<=n;i++) 
			if(i+L-1<=n) q.push((music){i,i+L-1,min(i+R-1,n),query(i+L-1,min(i+R-1,n))});//注意不要超出 n
		for(int i=1;i<=k;i++)
		{
			music now=q.top();q.pop();
			ans+=a[now.a]-a[now.s-1];//计算 fi(l,r) 
			if(now.a!=now.l) q.push((music){now.s,now.l,now.a-1,query(now.l,now.a-1)});
			if(now.a!=now.r) q.push((music){now.s,now.a+1,now.r,query(now.a+1,now.r)});
		}
		printf("%lld\n",ans);
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}