题目传送门(BZOJ)
>原文链接<

题解 :

题意就是在序列上选择长度在$[L, R]$间的不同的K个区间,求最大和。

由于每次选择对下次不存在影响,所以每次都贪心的选最好的一定是最优的。

首先求出前缀和,当我们钦定左端点为$i$的时候,一个最优的解一定是从$i+L-1$到$i+R-1$中选一个最大的。

那我们把这$n-L+1$个解扔到堆里,取一个堆顶。如果这次的堆顶是$i1$,为了下次还能选到最大的,我们要把$i1+L-1$到$i1+R-1$当中第二大的扔到堆里。做这个操作的前提条件是这段区间还有元素。

所以我们堆中维护一个$pair$,分别是最大值和对应的左端点,再对所有左端点存一下当前查到第几大了。

每次查询弹出一个元素,如果对应左端点已经取了的小于$R-L+1$,那就再查一个最大值扔到堆里。

很多人都写的ST表,但是区间静态第K大这种东西主席树还是很好想的吧。

代码 :

#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 500100;const int INF = 5e8+9;int Kth[N], s[N], t[N<<5];int ls[N<<5], rs[N<<5], root[N];priority_queue<pair<int, int>> q;int n, K, L, R;int ll[N], rr[N];void insert(int l, int r, int &p, int q, int x) { static int _; p = ++_; t[p] = t[q]+1 ; if(l == r) return; int mid = (l+r) >> 1; if(x <= mid) rs[p] = rs[q], insert(l, mid, ls[p], ls[q], x); else ls[p] = ls[q], insert(mid+1, r, rs[p], rs[q], x);}int inq(int l, int r, int p, int q, int k) { if(l == r) return l; int sizl = t[ls[q]]-t[ls[p]]; int mid = (l+r) >> 1; if(sizl >= k) return inq(l, mid, ls[p], ls[q], k); else return inq(mid+1, r, rs[p], rs[q], k-sizl);}int main() { scanf("%d%d%d%d", &n, &K, &L, &R); for(int i = 1; i <= n; i ++ ) { int x; scanf("%d", &x); s[i] = s[i-1]+x; insert(-INF, INF, root[i], root[i-1], s[i]); ll[i] = i+L-1, rr[i] = min(i+R-1, n); } for(int i = 1; i <= n-L+1; i ++ ) { ++Kth[i]; int kk = rr[i]-ll[i]-Kth[i]+2; int mxn = inq(-INF, INF, root[ll[i]-1], root[rr[i]], kk)-s[i-1]; q.push(make_pair(mxn, i)); } long long ans = 0; while(K -- ) { ans += q.top().first; int i = q.top().second; q.pop(); if(Kth[i] < rr[i]-ll[i]+1) { ++Kth[i]; int kk = rr[i]-ll[i]-Kth[i]+2; int mxn = inq(-INF, INF, root[ll[i]-1], root[rr[i]], kk)-s[i-1]; q.push(make_pair(mxn, i)); } } printf("%lld\n", ans);}