题目大意
求出序列中长度在 \([L,R]\) 中的所有区间的区间和前 \(k\) 大的区间的区间和。
思路分析
暴力做法是把所有符合条件的区间扔进堆里，再弹出 \(k\) 个，时间复杂度 \(O((n^2+k)\log n)\)，可以拿到 \(20\text{pts}\) 的好成绩。
但真的有必要全部加进去吗？不！
我们设五元组 \((l,r,x,y,w)\) 表示所有左端点在 \(x\)，右端点在 \([l,r]\) 之间的区间和最大的区间的右端点为 \(y\)，区间和为 \(w\)。
不难发现，如果 \(l,r,x\) 都是确定的，那么 \(y,w\) 也是确定的，即：
-
\(y\) 为区间 \([l,r]\) 内的最大的前缀和对应的下标。
-
\(w\) 可以通过 \(sum[y]-sum[x-1]\) 得到。
所以我们可以用线段树维护前缀和，\(O(\log n)\) 得到 \(l,r,x\) 对应的 \(y,w\)，所以 \((l,r,x)+O(\log n)=(l,r,x,y,w)\)。
那么我们开始时只需要将所有的 \((i+L-1,i+R-1,i),1\le i\le n-L+1\) 加入一个按 \(w\) 比较的大根堆，在弹出第一个即为所有符合条件的区间的最大值。
那其他的次大值呢？
不难发现，我们的最大值是通过 \(y\) 得到的，因此，只要我们把 \(y\) 扣掉，再插入堆，就可以得到次大值。
具体的说，当我们的堆顶是 \((l,r,x)\) 时，我们弹出堆顶，将 \(w\) 加入答案，并将 \((l,y-1,x)\) 和 \((y+1,r,x)\) 加入堆。
只需要重复上述过程 \(k\) 次就可以得到全部答案。
时间复杂度 \(O((n+k)\log n)\)。
代码
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N=500500;
#define int long long
#define PII pair<long long,long long>
#define mid (l+r>>1)
#define inf 0x3f3f3f3f3f3f3f3f
int n,k,L,R,ans;
int inp[N],sum[N];
struct Node{
int l,r,x,y,val;
}now;
bool operator < (Node a,Node b){
return a.val<b.val;
}
priority_queue <Node> q;
struct ST{
int maxn[N<<2],maxi[N<<2];
void build(int p,int l,int r){
if(l==r){maxn[p]=sum[l];maxi[p]=l;return ;}
build(p<<1,l,mid);build(p<<1|1,mid+1,r);
maxn[p]=max(maxn[p<<1],maxn[p<<1|1]);
maxi[p]=(maxn[p<<1]==maxn[p])?maxi[p<<1]:maxi[p<<1|1];
}
PII ask(int p,int l,int r,int x,int y){
if(x<=l&&r<=y) return {maxn[p],maxi[p]};
PII ls=(x<=mid)?ask(p<<1,l,mid,x,y):PII{-inf,-inf};
PII rs=(y>mid)?ask(p<<1|1,mid+1,r,x,y):PII{-inf,-inf};
return max(ls,rs);
}
}tree;
void insert(int l,int r,int x){
int maxi=tree.ask(1,1,n,l,r).second;
q.push(Node{l,r,x,maxi,sum[maxi]-sum[x-1]});
}
signed main(){
scanf("%lld%lld%lld%lld",&n,&k,&L,&R);
for(int i=1;i<=n;i++)
scanf("%lld",&inp[i]),sum[i]=sum[i-1]+inp[i];
tree.build(1,1,n);
for(int i=1;i<=n;i++)
if(i+L-1<=n) insert(i+L-1,min(i+R-1,n),i);
for(int i=1;i<=k;i++){
if(q.empty()) break;
now=q.top();q.pop();
ans+=now.val;
if(now.y!=now.r) insert(now.y+1,now.r,now.x);
if(now.y!=now.l) insert(now.l,now.y-1,now.x);
}
cout<<ans<<'\n';
return 0;
}