我好菜啊 _(:з」∠)_

本周智商下线。。。写啥都写不出来，学校数学课卡题卡到爆炸，考试抄错答题卡。呜呜呜

题目

给一个序列求长度在 [L, R] 间的前 k 大子段和。

代码

用堆维护一个三元组 (B, L, R) 表示从 B 开始，到 [L, R] 任意位置结束的最优情况。
然后每次贪心如果最优答案的终点在位置 M ，就先 pop 当前三元组，插入 (B, L, M-1) 和 (B, M+1, R)。

如何求出 (B, L, R) 这个三元组的最大和呢？
先求出前缀和，那么最优的位置可以通过 ST 表在前缀和上 RMQ 出来。
最终的答案就是前缀和上 Pre[M] - Pre[B - 1]

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#ifdef LCYTEST
#define logf(fmt, arg...) printf("[LOG] "fmt, ##arg)
#else
#define logf(fmt, arg...) { ; }
#endif
using namespace std;
const int MAX_N = int(2E6);
typedef long long LL;

struct seg {
    int B, L, R;
    pair<LL, int> S;
    
    seg(int B, int L, int R, pair<LL, int> S) :
        B(B), L(L), R(R), S(S) { }
    
    friend bool operator<(const seg &lhs, const seg &rhs) {
        return lhs.S.first < rhs.S.first;
    }
};

int N, K, L, R;
int Src[MAX_N];
LL Pre[MAX_N]; // Pre[n] repr [1, n]
LL Max[20][MAX_N];
int Maxid[20][MAX_N];
int Log2[MAX_N];

void make_st() {
    Log2[0] = -1;
    for(int i=1;i<=N;i++) {
        Log2[i] = Log2[i>>1] + 1;
    }
    
    for(int i=1;i<=N;i++) {
        Max[0][i] = Pre[i];
        Maxid[0][i] = i;
    }
    
    for(int j=1;j<=Log2[N];j++) {
        int c = (1 << j) - 1;
        for(int i=1;i+c<=N;i++) {
            Max[j][i] = max(Max[j-1][i], Max[j-1][i + (1 << (j-1))]);
            Maxid[j][i] = (Max[j][i] == Max[j-1][i] ?
                Maxid[j-1][i] : Maxid[j-1][i + (1 << (j-1))]);
        }
    }
}

pair<LL, int> query(int L, int R) { // Query on [L, R]
    int k = Log2[R - L + 1];
    LL a = Max[k][L];
    LL b = Max[k][R - (1 << k) + 1];
    return make_pair(max(a, b), (a>=b?Maxid[k][L]:Maxid[k][R-(1<<k)+1]));
}

LL work() {
    priority_queue<seg> PQ;

    for(int i=1;i<=N;i++) {
        if(i+L-1 <= N) {
            int t = min(N, i+R-1);
            pair<LL, int> tmp = query(i+L-1, t);
            tmp.first -= Pre[i-1];
            PQ.push(seg(i, i+L-1, t, tmp));
        }
    }
    
    int k = K;
    LL ret = 0LL;
    while(!PQ.empty() && k) {
        seg cur = PQ.top(); PQ.pop();
        
        ret += cur.S.first;
        
        int M = cur.S.second;
        
        logf("Sel [%d, %d] = %d\n", cur.B, cur.S.second, cur.S.first);
        
        if(cur.L < M) {
            pair<LL, int> tmp = query(cur.L, M-1);
            tmp.first -= Pre[cur.B-1];
            logf("Ins [%d, (%d %d)] = %d\n", cur.B, cur.L, M-1, tmp.first);
            PQ.push(seg(cur.B, cur.L, M-1, tmp));
        }
        
        if(M < cur.R) {
            pair<LL, int> tmp = query(M+1, cur.R);
            tmp.first -= Pre[cur.B-1];
            logf("Ins [%d, (%d %d)] = %d\n", cur.B, M+1, R, tmp.first);
            PQ.push(seg(cur.B, M+1, cur.R, tmp));
        }
        
        k--;
    }
    
    return ret;
}

int main() {
    scanf("%d %d %d %d", &N, &K, &L, &R);
    
    for(int i=1;i<=N;i++) {
        scanf("%d", &Src[i]);
        Pre[i] = Pre[i-1] + Src[i];
    }
    
    make_st();
    
    printf("%lld\n", work());
}