quhengyi11 的博客

题解 P2048 【[NOI2010]超级钢琴】

posted on 2018-12-13 22:23:43 | under 题解 |

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define N 2200005
#define ls(u) t[u].s[0]
#define rs(u) t[u].s[1]
#define mod 51061
#define ll long long
int a[N], n, m, L, R, len, st[N][23];
ll ans;
inline int query (int l, int r)
{
len = log(r - l + 1) / log(2);
return a[st[l][len]] > a[st[r - (1 << len) + 1][len]] ? st[l][len] : st[r - (1 << len) + 1][len];
}
struct node{
int z, l, r, v;
node (int z, int l, int r) : z(z), l(l), r(r), v(query(l, r)) {}
friend bool operator < (node x, node y) {return a[x.v] - a[x.z] < a[y.v] - a[y.z];}
};
std::priority_queue<node> q;
int main ()
{
scanf("%d %d %d %d", &n, &m, &L, &R);
fo (i, 1, n) {scanf("%d", &a[i]); a[i] += a[i - 1]; st[i][0] = i;}
fo (j, 1, 20)
fo (i, 1, n)
st[i][j] = a[st[i][j - 1]] > a[st[i + (1 << j - 1)][j - 1]] ? st[i][j - 1] : st[i + (1 << j - 1)][j - 1];
fo (i, 1, n)
if (i + L - 1 <= n)
q.push(node(i - 1, i + L - 1, std::min(i + R - 1, n)));
fo (i, 1, m)
{
node tmp = q.top(); q.pop();
ans += a[tmp.v] - a[tmp.z];
if (tmp.v != tmp.l) q.push(node(tmp.z, tmp.l, tmp.v - 1));
if (tmp.v != tmp.r) q.push(node(tmp.z, tmp.v + 1, tmp.r));
}
printf("%lld\n", ans);
}