1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#define maxn 500010
#define cQ const Queue
#define ll long long
using namespace std;
int n, m, L, R;
int s[maxn], b[maxn], cnt;
void init_hash() {
for (int i = 1; i <= n; ++i) b[i] = s[i];
sort(b + 1, b + n + 1); cnt = unique(b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= n; ++i) s[i] = lower_bound(b + 1, b + cnt + 1, s[i]) - b;
}
#define lc T[i].ch[0]
#define rc T[i].ch[1]
#define Lc T[j].ch[0]
#define Rc T[j].ch[1]
struct zhuxi {
int v, ch[2];
} T[maxn * 20]; int top, rt[maxn];
void update(int &i, int j, int l, int r, int k, int v) {
i = ++top; T[i] = T[j]; T[i].v += v;
if (l == r) return ; int m = l + r >> 1;
if (k <= m) update(lc, Lc, l, m, k, v);
else update(rc, Rc, m + 1, r, k, v);
}
int query(int i, int j, int l, int r, int k) {
if (l == r) return l;
int m = l + r >> 1, v = T[Rc].v - T[rc].v;
if (k <= v) return query(rc, Rc, m + 1, r, k);
else return query(lc, Lc, l, m, k - v);
}
struct Queue {
int i, v, k;
Queue() {}
Queue(int _i, int _v, int _k) { i = _i; v = _v; k = _k; }
friend bool operator < (cQ &u, cQ &v) { return u.v < v.v; }
} ; priority_queue<Queue> Q;
ll ans;
int main() {
cin >> n >> m >> L >> R;
for (int i = 1; i <= n; ++i) {
int x; scanf("%d", &x);
s[i] = s[i - 1] + x;
} init_hash();
for (int i = 1; i <= n; ++i) update(rt[i], rt[i - 1], 1, cnt, s[i], 1);
for (int i = 1; i + L - 1 <= n; ++i) {
int v = b[query(rt[i + L - 2], rt[min(n, i + R - 1)], 1, cnt, 1)] - b[s[i - 1]];
Q.push(Queue(i, v, 1));
}
for (int i = 1; i <= m; ++i) {
Queue u = Q.top(); Q.pop(); ans += u.v;
if (u.k + 1 > min(n, u.i + R - 1) - (u.i + L - 1) + 1) continue;
int v = b[query(rt[u.i + L - 2], rt[min(n, u.i + R - 1)], 1, cnt, u.k + 1)] - b[s[u.i - 1]];
Q.push(Queue(u.i, v, u.k + 1));
} cout << ans << endl;
return 0;
}
|