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

Posted on Symbols count in article: 1.3k Reading time ≈ 5 mins.

Problem

【NOI2010】超级钢琴

Time  Limit:  20  Sec\mathrm{Time\;Limit:\;20\;Sec}
Memory  Limit:  512  MB\mathrm{Memory\;Limit:\;512\;MB}

Description

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

Input

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

Output

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

Sample Input

1
2
3
4
5
4 3 2 3
3
2
-6
8

Sample Output

1
11

Explanation

共有55种不同的超级和弦：
音符1∼21\sim2，美妙度为3+2=53 + 2 = 5
音符2∼32\sim3，美妙度为2+(−6)=−42 + (-6) = -4
音符3∼43\sim4，美妙度为(−6)+8=2(-6) + 8 = 2
音符1∼31\sim3，美妙度为3+2+(−6)=−13 + 2 + (-6) = -1
音符2∼42\sim4，美妙度为2+(−6)+8=42 + (-6) + 8 = 4
最优方案为：乐曲由和弦11,和弦33,和弦55组成，美妙度为5+2+4=115 + 2 + 4 = 11。

HINT

N≤5×105N\le5\times10^5，k≤5×105k\le5\times10^5，−1000≤Ai≤1000-1000\le A_i\le1000，1≤L≤R≤N1\le L\le R\le N
数据保证一定存在满足条件的乐曲

标签：堆 ST表

Solution

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

找出第kk大的差值，可以用一个堆维护，每次弹出堆顶。
首先将区间和处理为前缀和，这样问题变为给出一个数组{sn}\lbrace s_n\rbrace，求第kk大的si−sjs_i-s_j，其中i,j∈[1,n],  i−R≤j≤i−Li,j\in[1,n],\;i-R\le j\le i-L。
考虑对于一个确定的sjs_j，使差值最大的sis_i一定是si−R∼si−Ls_{i-R}\sim s_{i-L}中的最小值，这个最小值可以在O(1)O(1)时间内用ST表找到。这个值取完后，对于其他以jj作为终点的区间可以分成两部分，一部分为起点在i−R∼j−1i-R\sim j-1间的区间，另一部分为起点在j+1∼i−Lj+1\sim i-L的区间，在这两个区间中分别找最大值插入堆中。
对于以每个位置为右端点的区间，我们维护四元组(p,l,r,val)(p,l,r,val)，代表右端点位置，左端点的左右界，以及在此左右界中的最大差值。一开始插入以每个位置为右端点的区间中和最大的区间，随后每次弹出最大区间，将这个四元组拆成两部分，即若当前四元组为(p,l,r,val)(p,l,r,val)，左端点取tt时得到最大差值，以后不能取tt，将四元组拆为(p,l,t−1,val1)(p,l,t-1,val_1)和(p,t+1,r,val2)(p,t+1,r,val_2)，其中val1val_1和val2val_2分别表示左端点在[l,t−1][l,t-1]和[t+1,r][t+1,r]间时的最大差值。
如此即可在O(nlog⁡n)O(n\log{n})的时间内找到前kk大差值的和。

Code

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
#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;
}