题解区里没有的 $O(N \log ^ 2 N)$ 典中典算法。

先求出 $A$ 的前缀和 $S$，答案为前 $k$ 大的 $S_i - S_j$ 之和，其中 $i$、$j$ 满足 $L \le i - j \le R$

注意到前 $k$ 大特别显眼，考虑二分第 $k$ 大值。假设此时二分到答案 $mid$，即第 $k$ 大值是否 $\ge mid$，可行性判定即为满足 $S_i - S_j \ge mid$ 的点对 $(i, j)$ 个数是否 $\ge k$。

转换一下条件，就是求 $\sum _ {i=0} ^ n \sum _ {j=0} ^ {i-1} [S_j \le S_i - mid]$ 是否 $\ge k$

于是先离散化一下，然后简单扫描线 + 树状数组优化掉 $j$ 那一层，单次判定 $O(N \log N)$。

由于每一次清空树状数组常数巨大，可以给每个节点打 tag，若有节点需要访问或修改时再清空（参考 OI-Wiki）

代码如下：

#include <bits/stdc++.h>
using namespace std;
template <class Tp> void read(Tp &a) {
    int s = 1, ch; a = 0;
    do if ((ch = getchar()) == '-') s = -1; while (ch < '0' || ch > '9');
    while (ch >= '0' && ch <= '9') a = a * 10 + ch - '0', ch = getchar();
    a = a * s;
}
template <class Tp> void write(const Tp &a) {
    if (a < 0) return putchar('-'), write(-a);
    if (a >= 10) write(a / 10);
    putchar('0' + a % 10);
}
#define mid (l + r >> 1)
#define ll long long
struct pii { int x; ll y; }; pii operator+(const pii &a, const pii &b) { return {a.x + b.x, a.y + b.y}; }
const int N = 5e5 + 5, inf = 5e8;
int n, k, L, R, a[N], s[N];
namespace mp {
    int ori[N], tot;
    void init() {
        for (int i = 0; i <= n; i++) ori[++tot] = s[i];
        sort(ori + 1, ori + tot + 1), tot = unique(ori + 1, ori + 1 + tot) - ori - 1;
    }
    int getle(int x) { return upper_bound(ori + 1, ori + tot + 1, x) - ori - 1; }
    int getlt(int x) { return lower_bound(ori + 1, ori + tot + 1, x) - ori - 1; }
}
namespace bit {
    int cnt[N], tag[N], now; ll sum[N];
    #define lb(i) (i & -i)
    void clear() { now++; }
    void insert(int j) {
        for (int i = j; i <= mp::tot; i += lb(i)) {
            tag[i] != now && (tag[i] = now, cnt[i] = sum[i] = 0);
            cnt[i]++, sum[i] += mp::ori[j];
        }
    }
    void erase(int j) {
        for (int i = j; i <= mp::tot; i += lb(i)) {
            tag[i] != now && (tag[i] = now, cnt[i] = sum[i] = 0);
            cnt[i]--, sum[i] -= mp::ori[j];
        }
    }
    pii ask(int j) {
        pii res = {0, 0};
        for (int i = j; i; i -= lb(i)) {
            tag[i] != now && (tag[i] = now, cnt[i] = sum[i] = 0);
            res = res + pii{cnt[i], sum[i]};
        }
        return res;
    }
}
inline int check(int lim) {
    ll res = 0; bit::clear();
    for (int i = L; i <= n; i++) {
        bit::insert(mp::getle(s[i - L]));
        if (i - R - 1 >= 0) bit::erase(mp::getle(s[i - R - 1]));
        res += bit::ask(mp::getle(s[i] - lim)).x;
        if (res >= k) return 1;
    }
    return 0;
}
inline ll sumup(int k, int lim) {
    ll res = 0, cnt = 0; bit::clear();
    for (int i = L; i <= n; i++) {
        bit::insert(mp::getle(s[i - L]));
        if (i - R - 1 >= 0) bit::erase(mp::getle(s[i - R - 1]));
        auto [t1, t2] = bit::ask(mp::getlt(s[i] - lim));
        res += 1ll * t1 * s[i] - t2, cnt += t1;
    }
    res += (k - cnt) * lim;
    return res;
}
main() {
    ios::sync_with_stdio(0), cin.tie(0);
    read(n), read(k), read(L), read(R);
    for (int i = 1; i <= n; i++) read(a[i]);
    for (int i = 0; i <= n; i++) s[i] = s[i - 1] + a[i];
    mp::init();
    int l = -inf, r = inf, ans = inf + 1;
    while (l <= r) check(mid) ? (ans = mid, l = mid + 1) : (r = mid - 1);
    write(sumup(k, ans)), putchar('\n');
    return 0;
}