http://www.lydsy.com/JudgeOnline/problem.php?id=2006 (题目链接)
题意
给出一个数列，在其中选出K个长度在${[L,R]}$之间的不同的区间，使得他们的和权值和最大。
Solution
我们可以先处理处它的前缀和${sum}$，然后用ST表维护前缀和的区间最小值。做完这些预处理以后，我们从L for 到n，每次在区间${[i-R,i-L]}$中取出前缀和最小的${sum[M]}$，与${sum[i]}$相减，丢入堆中。之后我们每次取出堆顶元素加入答案，并分别找出区间${[i-R,M-1]}$和${[M+1,i-L]}$的前缀和最小的${sum[M1],sum[M2]}$，分别相减，丢入堆中。以此类推，直到取出${K}$个元素为止。
代码
// bzoj2006
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define LL long long
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
inline int getint() {
int x=0,f=1;char ch=getchar();
while (ch>'9' || ch<'0') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
} const int maxn=500010;
struct data {
int l,r,m,i;LL w;
friend bool operator < (const data &a,const data &b) {
return a.w<b.w;
}
};
priority_queue<data> q;
int ST[maxn][30],bin[30],a[maxn],Log[maxn];
LL s[maxn];
int n,K,L,R; inline int mina(register int x,register int y) {
return s[x]<s[y] ? x : y;
}
inline int query(register int l,register int r) {
int k=Log[r-l+1];
return mina(ST[l][k],ST[r-bin[k]+1][k]);
}
int main() {
bin[0]=1;for (int i=1;i<=19;i++) bin[i]=bin[i-1]<<1;
n=getint(),K=getint(),L=getint(),R=getint();
for (int i=1;i<=n;i++) s[i]=getint(),s[i]+=s[i-1];
for (int i=1;i<=n;i++) ST[i][0]=i;
for (int i=2;i<=n;i++) Log[i]=Log[i>>1]+1;
for (int j=1;j<=19;j++)
for (int i=0;i+bin[j]<=n+1;i++)
ST[i][j]=mina(ST[i][j-1],ST[i+bin[j-1]][j-1]);
for (int i=L;i<=n;i++) {
int l=max(i-R,0),r=i-L;
int x=query(l,r);
q.push((data){l,r,x,i,s[i]-s[x]});
}
LL ans=0;
while (K--) {
data t=q.top();ans+=t.w;q.pop();
if (t.l<t.m) {
int x=query(t.l,t.m-1);
q.push((data){t.l,t.m-1,x,t.i,s[t.i]-s[x]});
}
if (t.m<t.r) {
int x=query(t.m+1,t.r);
q.push((data){t.m+1,t.r,x,t.i,s[t.i]-s[x]});
}
}
printf("%lld",ans);
return 0;
}