题目描述见链接 .
题目即让我们求前 大的连续子段和 .
考虑将每个左端点 提出, 使用 表 求出每个左端点最佳的右端点, 将其扔进 大根堆 中,
每次取出堆顶元素 , 累加进答案, 在 中分别寻找新的右端点, 再放入堆中 .
时间复杂度 .
- 大根堆 中维护
struct Fuck
, 内存有左端点, 以及右端点的活动区间 和 当前区间右端点 .
#include<bits/stdc++.h>
#define reg register
#define fi first
#define se second
typedef long long ll;
typedef std::pair<int, int> pr;
typedef std::pair<int, pr> ppr;
int read(){
int s = 0, flag = 1;
char c;
while((c=getchar()) && !isdigit(c))
if(c == '-'){ c = getchar(), flag = -1; break ; }
while(isdigit(c)) s = s*10 + c-'0', c = getchar();
return s * flag;
}
const int maxn = 500005;
int N;
int K;
int L;
int R;
int A[maxn];
int lg[maxn];
int sum[maxn];
pr st[maxn][20];
pr stq(const int &l, const int &r){ return std::max(st[l][lg[r-l+1]], st[r-(1<<lg[r-l+1])+1][lg[r-l+1]]); }
struct Fuck{
int lt, l, r, rt;
Fuck(int lt=0, int l=0, int r=0):lt(lt), l(l), r(r), rt(stq(l, r).se) {}
friend bool operator < (const Fuck &a, const Fuck &b){ return sum[a.rt]-sum[a.lt-1] < sum[b.rt]-sum[b.lt-1]; }
} ;
int main(){
N = read(), K = read(), L = read(), R = read();
for(reg int i = 1; i <= N; i ++) A[i] = read(), sum[i] = sum[i-1] + A[i], st[i][0] = pr(sum[i], i);
for(reg int i = 1; i <= N; i ++){
lg[i] = lg[i-1];
while((1<<lg[i]+1) <= i) lg[i] ++;
}
for(reg int j = 1; j <= 19; j ++)
for(reg int i = 1; i+(1<<j)-1 <= N; i ++) st[i][j] = std::max(st[i][j-1], st[i+(1<<j-1)][j-1]);
std::priority_queue < Fuck > Q;
for(reg int i = 1; i <= N; i ++){
int lt = i+L-1; if(lt > N) continue ;
int rt = std::min(N, i+R-1); pr t = stq(lt, rt);
Q.push(Fuck(i, lt, rt));
}
ll Ans = 0;
while((K --) && !Q.empty()){
Fuck t = Q.top(); Q.pop();
Ans += sum[t.rt] - sum[t.lt-1];
if(t.l <= t.rt-1) Q.push(Fuck(t.lt, t.l, t.rt-1));
if(t.rt+1 <= t.r) Q.push(Fuck(t.lt, t.rt+1, t.r));
}
printf("%lld
", Ans);
return 0;
}