BZOJ2006【NOI2010】超级钢琴 < ST表+堆 >

Problem

【NOI2010】超级钢琴

Description

是一个小有名气的钢琴家，最近送给了一架超级钢琴，希望能够用这架钢琴创作出世界上最美妙的音乐。
这架超级钢琴可以弹奏出个音符，编号为。第个音符的美妙度为，其中可正可负。
一个“超级和弦“由若干个编号连续的音符组成，包含的音符个数不少于且不多于。我们定义超级和弦的美妙度为其包含的所有音符的美妙度之和。两个超级和弦被认为是相同的，当且仅当这两个超级和弦所包含的音符集合是相同的。
决定创作一首由个超级和弦组成的乐曲，为了使得乐曲更加动听，要求该乐曲由个不同的超级和弦组成。我们定义一首乐曲的美妙度为其所包含的所有超级和弦的美妙度之和。想知道他能够创作出来的乐曲美妙度最大值是多少。

Input

第一行包含四个正整数。其中为音符的个数，为乐曲所包含的超级和弦个数，和分别是超级和弦所包含音符个数的下限和上限。
接下来行，每行包含一个整数，表示按编号从小到大每个音符的美妙度。

Output

只有一个整数，表示乐曲美妙度的最大值。

Sample Input

Sample Output

Explanation

共有种不同的超级和弦：
音符，美妙度为
音符，美妙度为
音符，美妙度为
音符，美妙度为
音符，美妙度为
最优方案为：乐曲由和弦,和弦,和弦组成，美妙度为。

HINT

，，，
数据保证一定存在满足条件的乐曲

标签：堆 ST表

Solution

经典线段树例题，不过我用的是一种精妙的ST表。

找出第大的差值，可以用一个堆维护，每次弹出堆顶。
首先将区间和处理为前缀和，这样问题变为给出一个数组，求第大的，其中。
考虑对于一个确定的，使差值最大的一定是中的最小值，这个最小值可以在时间内用ST表找到。这个值取完后，对于其他以作为终点的区间可以分成两部分，一部分为起点在间的区间，另一部分为起点在的区间，在这两个区间中分别找最大值插入堆中。
对于以每个位置为右端点的区间，我们维护四元组，代表右端点位置，左端点的左右界，以及在此左右界中的最大差值。一开始插入以每个位置为右端点的区间中和最大的区间，随后每次弹出最大区间，将这个四元组拆成两部分，即若当前四元组为，左端点取时得到最大差值，以后不能取，将四元组拆为和，其中和分别表示左端点在和间时的最大差值。
如此即可在的时间内找到前大差值的和。

Code

#include <bits/stdc++.h>
#define MAX_N 500000
#define LOG Log[t-s]
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, L, R, s[MAX_N+5], st[MAX_N+5][25], Log[MAX_N+5];
struct node {int p, l, r, val; bool operator < (const node &t) const {return t.val > val;}} ;
priority_queue <node> que;
int Min(int a, int b) {return s[a] < s[b] ? a : b;}
int query(int s, int t) {return s > t ? -1 : Min(st[s][LOG], st[t-(1<<LOG)+1][LOG]);}
int main() {
    read(n), read(m), read(L), read(R); lnt ans = 0;
    for (int i = 2; i <= n; i++) Log[i] = Log[i>>1]+1;
    for (int i = 1; i <= n; i++) read(s[i]), s[i] += s[i-1], st[i][0] = i;
    for (int j = 1; (1<<j) <= n; j++) for (int i = 0; i <= n-(1<<j)+1; i++)
        st[i][j] = Min(st[i][j-1], st[i+(1<<(j-1))][j-1]);
    for (int i = L; i <= n; i++)
        que.push((node){i, max(i-R, 0), i-L, s[i]-s[query(max(i-R, 0), i-L)]});
    for (int i = 1, t, p; i <= m; i++) {
        node tp = que.top(); que.pop(), ans += tp.val, p = tp.p;
        int ll = tp.l, rr = tp.r, lr = query(ll, rr)-1, rl = query(ll, rr)+1;
        if (~(t = query(ll, lr))) que.push((node){p, ll, lr, s[p]-s[t]});
        if (~(t = query(rl, rr))) que.push((node){p, rl, rr, s[p]-s[t]});
    }
    return printf("%lld\n", ans), 0;
}