BZOJ2006 [NOI2010]超級鋼琴 【堆 + RMQ】

2006: [NOI2010]超級鋼琴

Time Limit:?20 Sec??Memory Limit:?552 MB
Submit:?3446??Solved:?1692
[Submit][Status][Discuss]

Description

小Z是一個小有名氣的鋼琴家，最近C博士送給了小Z一架超級鋼琴，小Z希望能夠用這架鋼琴創作出世界上最美妙的

音樂。 這架超級鋼琴可以彈奏出n個音符，編號為1至n。第i個音符的美妙度為Ai，其中Ai可正可負。 一個“超級

和弦”由若干個編號連續的音符組成，包含的音符個數不少于L且不多于R。我們定義超級和弦的美妙度為其包含的

所有音符的美妙度之和。兩個超級和弦被認為是相同的，當且僅當這兩個超級和弦所包含的音符集合是相同的。?

小Z決定創作一首由k個超級和弦組成的樂曲，為了使得樂曲更加動聽，小Z要求該樂曲由k個不同的超級和弦組成。

我們定義一首樂曲的美妙度為其所包含的所有超級和弦的美妙度之和。小Z想知道他能夠創作出來的樂曲美妙度最

大值是多少。

Input

第一行包含四個正整數n, k, L, R。其中n為音符的個數，k為樂曲所包含的超級和弦個數，L和R分別是超級和弦所

包含音符個數的下限和上限。 接下來n行，每行包含一個整數Ai，表示按編號從小到大每個音符的美妙度。

N<=500,000

k<=500,000

-1000<=Ai<=1000,1<=L<=R<=N且保證一定存在滿足條件的樂曲

Output

只有一個整數，表示樂曲美妙度的最大值。

Sample Input

4 3 2 3
3
2
-6
8

Sample Output

11

【樣例說明】
共有5種不同的超級和弦：
音符1 ~ 2，美妙度為3 + 2 = 5
音符2 ~ 3，美妙度為2 + (-6) = -4
音符3 ~ 4，美妙度為(-6) + 8 = 2
音符1 ~ 3，美妙度為3 + 2 + (-6) = -1
音符2 ~ 4，美妙度為2 + (-6) + 8 = 4
最優方案為：樂曲由和弦1，和弦3，和弦5組成，美妙度為5 + 2 + 4 = 11。

我們利用前綴和可以很快得到最大的答案

對于每個點i，我們只要求出sum[i + L - 1] 到 sum[i + R - 1]中最大的值就可以得到以i為左端點的最大值

我們設這樣一個值為三元組(i,l,r)的值，表示以i開頭右端點在[l,r]內的區間最大和

利用這個，我們求出最大值后，求第二大的值可能以其它i開頭，也可能仍然以當前i開頭，我們就把當前(i,l,r)分裂成

(i,l,t - 1)和(i,t + 1,r)就可以了

重復K次，即得結果

但是如何做到快速求區間最大值呢？

這就用到了RMQ算法【ST表】

ST表是用以解決區間最大值無修改的算法，預處理O(nlogn),查詢O(1)

可以說在沒有修改的情況下比線段樹優很多

具體實現：

預處理

我們設mx[i][j]表示以[i,i + 2^j - 1]，也就是以i開頭長度為2^j的區間的最大值

利用倍增的方法，mx[i][j] = max(mx[i][j - 1],mx[i + 2^(j - 1)][j - 1]);

我們可以處理出所有的mx【但是要注意數組不要越界】

查詢

我們要查詢的區間長度是2的n次方很好辦，就是mx[i][n]

但是如果不是呢？

我們可以把原區間分成兩個相交的2^n的區間，求二者的最大值即可

具體區間為[l,r]，我們令t = log2(r - l + 1)，則ans = max(mx[l][t],mx[r - 2^t?+ 1][t]);

最后我們就可以A啦

【STL似乎不會T】

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#define mp(a,b,c,d) (node){a,b,c,d}
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
using namespace std;
const int maxn = 500005,maxm = 100005,INF = 1000000000;
inline int RD(){int out = 0,flag = 1; char c = getchar();while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}return out * flag;
}
int N,K,L,R,sum[maxn],mx[maxn][30],Log[maxn];
LL ans = 0;
struct node{int i,l,r,t;};
inline bool operator <(const node& a,const node& b){return sum[a.t] - sum[a.i - 1] < sum[b.t] - sum[b.i - 1];}
priority_queue<node,vector<node> > q;
void RMQ(){Log[0] = -1;for (int i = 1; i <= N; i++) Log[i] = Log[i >> 1] + 1;int t = Log[N];REP(i,N) mx[i][0] = i;for (int i = N; i; i--){for (int j = 1; j <= t; j++){if (i + (1 << j) - 1 > N) break;int t1 = mx[i][j - 1],t2 = mx[i + (1 << j - 1)][j - 1];mx[i][j] = sum[t1] > sum[t2] ? t1 : t2;}}
}
inline int Query(int l,int r){if (l == r) return l;int t = Log[r - l + 1],t1 = mx[l][t],t2 = mx[r - (1 << t) + 1][t];return sum[t1] > sum[t2] ? t1 : t2;
}
void solve(){node u;REP(i,N){if (i + L - 1 > N) break;int r = min(i + R - 1,N);q.push(mp(i,i + L - 1,r,Query(i + L - 1,r)));}for (int i = 1; i <= K; i++){u = q.top(); q.pop();ans += sum[u.t] - sum[u.i - 1];if (u.t - 1 >= u.l) q.push(mp(u.i,u.l,u.t - 1,Query(u.l,u.t - 1)));if (u.t + 1 <= u.r) q.push(mp(u.i,u.t + 1,u.r,Query(u.t + 1,u.r)));}
}
int main(){N = RD(); K = RD(); L = RD(); R = RD();REP(i,N) sum[i] = sum[i - 1] + RD();RMQ();solve();cout<<ans<<endl;return 0;
}