[BZOJ 2006] [NOI 2010]超级钢琴(贪心+ST表+堆)
题面
给出一个长度为n的序列,选k段长度在L到R之间的区间，一个区间的值等于区间内所有元素之的和，使得k个区间的值之和最大。区间可以相交或包含，但一个区间只能被选1次.
\(n,k,L,R \leq 5 \times 10^5\)
分析
先把区间和转化成前缀和.枚举左端点\(i\),右端点的范围为\([i+L-1,\min(i+R-1,n)]\).在这个区间里面找一个前缀和最大的位置p,答案就是\(sum[p]-sum[i-1]\).静态维护区间最大值位置可以用ST表做。
但是我们要求k个最大区间，只把每个左端点对应的最大答案求出来，可能不够k个。对于每个左端点暴力枚举所有区间，把所有的值加入堆，最后取出k个显然也会超时。
我们维护一个堆(实现上用STL优先队列),堆里面的每个元素都是一个三元组\((i,l,r)\).表示区间左端点在\(i\),右端点在\([l,r]\)内时能取到的最大值.设\(f_m(l,r)\)为\([L,R]\)内的最大值位置，那么我们按照\(sum[f_m(l,r)]-sum[i]\)维护一个最大堆。初始时把\((i,i+L-1,min(i+R-1,n))\)插入堆。每次取堆顶\((i,l,r),\)累加堆顶的值。令\(f_m(l,r)=p\)，那次大值对应的区间右端点应该在\([l,p-1]\)或\([p+1,r]\)内。于是弹出堆顶，插入\((i,l,p-1),(i,p+1,r)\)。这样做k次，就可以求出答案。
ST表查询是\(O(1)\)的，故总时间复杂度为\(O((n+k)\log n)\)
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 500000
#define maxlogn 25
using namespace std;
typedef long long ll;
int n,k,L,R;
struct sparse_table{
int log2[maxn+5];
int st[maxn+5][maxlogn+5];
void ini(ll *a,int n){
log2[0]=-1;
for(int i=1;i<=n;i++) log2[i]=log2[i>>1]+1;
for(int i=1;i<=n;i++) st[i][0]=i;
for(int j=1;j<=log2[n]+1;j++){
for(int i=1;i+(1<<(j-1))<=n;i++){
if(a[st[i][j-1]]>a[st[i+(1<<(j-1))][j-1]]) st[i][j]=st[i][j-1];
else st[i][j]=st[i+(1<<(j-1))][j-1];
}
}
}
int query(ll *a,int l,int r){
int k=log2[r-l+1];
if(a[st[l][k]]>a[st[r-(1<<k)+1][k]]) return st[l][k];
else return st[r-(1<<k)+1][k];
}
}T;
int a[maxn+5];
ll sum[maxn+5];
struct node{
int l;
int r;
int i;
inline ll val(){
return sum[T.query(sum,l,r)]-sum[i-1];
}
node(){
}
node(int _i,int _l,int _r){
i=_i;
l=_l;
r=_r;
}
friend bool operator < (node p,node q){
return p.val()<q.val();
}
};
priority_queue<node>q;
int main(){
scanf("%d %d %d %d",&n,&k,&L,&R);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
}
T.ini(sum,n);
for(int i=1;i+L-1<=n;i++){
q.push(node(i,i+L-1,min(i+R-1,n)));
}
ll ans=0;
for(int i=1;i<=k;i++){
node now=q.top();
q.pop();
ans+=now.val();
int p=T.query(sum,now.l,now.r);
if(p>now.l) q.push(node(now.i,now.l,p-1));
if(p<now.r) q.push(node(now.i,p+1,now.r));
}
printf("%lld\n",ans);
}