给定一个序列，从中选出求k段连续区间，使总和最大。区间长度属于[L,R]。

链接

BZOJ2006

COGS

题解

很巧妙的思路。

首先创建一个大根堆，堆里每个元素有四个参数：x,l,r,y。x为选出的这段区间的起点，l,r为区间终点的范围。y为所有[x,y]区间和取到最大值的位置。每次从堆顶取出一个元素，累加到答案中后，将[l,r]拆分为[l,y-1]和[y+1,r]两部分，作为两个新的元素添加到堆中。因为当[x,y]的区间和取到最大值后，次大值一定在剩余的两部分中取到。然后依次取出k组元素后即得答案。

在求最大值在何处取到时，需要提前拿RMQ预处理一波。这样可以在O(1)的时间内求区间最大值得位置了。

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define N 1000010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,k,l,r,i;
int f[N][25];
LL Ans;
LL a[N],s[N];

struct Data{
    int x,l,r,y;
};

bool operator <(Data a,Data b){
    return (s[a.y]-s[a.x-1])<(s[b.y]-s[b.x-1]);
}

priority_queue <Data> Q;

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &x,int &y){x^=y^=x^=y;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

inline int Query(int x,int y){
    int p=(int)log2(y-x+1);
    if (x==y)   return x;
    return (s[f[x][p]]>s[f[y-(1<<p)+1][p]])?f[x][p]:f[y-(1<<p)+1][p];
}

inline void Ready(){
    int i=0,j=0;
    for (i=1;i<=n;i++)  s[i]=s[i-1]+a[i],f[i][0]=i;
    for (j=1;j<=19;j++)
        for (i=1;i+(1<<j)-1<=n;i++)
            f[i][j]=(s[f[i][j-1]]>s[f[i+(1<<(j-1))][j-1]])?f[i][j-1]:f[i+(1<<(j-1))][j-1];
    for (i=1;i<=n;i++)
        if (i+l-1<=n)   Q.push((Data){i,i+l-1,Min(i+r-1,n),Query(i+l-1,Min(i+r-1,n))});
}

inline void Work(){
    Data x;
    Ans=0;
    while (k--){
        x=Q.top();  Q.pop();
        if (Q.empty())  break;
        Ans+=s[x.y]-s[x.x-1];
        if (x.y>x.l)    Q.push((Data){x.x,x.l,x.y-1,Query(x.l,x.y-1)});
        if (x.y<x.r)    Q.push((Data){x.x,x.y+1,x.r,Query(x.y+1,x.r)});
    }
    cout<<Ans<<endl;
}

int main(){
    n=read();   k=read();   l=read();   r=read();
    for (i=1;i<=n;i++)  a[i]=read();
    Ready();    Work();
    return 0;
}