P2048 [NOI2010] 超级钢琴
题目描述
小 Z 是一个小有名气的钢琴家，最近 C 博士送给了小 Z 一架超级钢琴，小 Z 希望能够用这架钢琴创作出世界上最美妙的音乐。
这架超级钢琴可以弹奏出 n 个音符，编号为 1 至 n。第 i 个音符的美妙度为 A_i，其中 A_i 可正可负。
一个“超级和弦”由若干个编号连续的音符组成，包含的音符个数不少于 L 且不多于 R。我们定义超级和弦的美妙度为其包含的所有音符的美妙度之和。两个超级和弦被认为是相同的，当且仅当这两个超级和弦所包含的音符集合是相同的。
小 Z 决定创作一首由 k 个超级和弦组成的乐曲，为了使得乐曲更加动听，小 Z 要求该乐曲由 k 个不同的超级和弦组成。我们定义一首乐曲的美妙度为其所包含的所有超级和弦的美妙度之和。小 Z 想知道他能够创作出来的乐曲美妙度最大值是多少。
输入格式
输入第一行包含四个正整数 n, k, L, R。其中 n 为音符的个数，k 为乐曲所包含的超级和弦个数，L 和 R 分别是超级和弦所包含音符个数的下限和上限。
接下来 n 行，每行包含一个整数 A_i，表示按编号从小到大每个音符的美妙度。
输出格式
输出只有一个整数，表示乐曲美妙度的最大值。
输入输出样例 #1
输入 #1
4 3 2 3
3
2
-6
8
输出 #1
11
说明/提示
样例解释
共有 5 种不同的超级和弦：
- 音符 1 \sim 2，美妙度为 3+2=5；
- 音符 2 \sim 3，美妙度为 2+(-6)=-4；
- 音符 3 \sim 4，美妙度为 (-6)+8=2；
- 音符 1 \sim 3，美妙度为 3+2+(-6)=-1；
- 音符 2 \sim 4，美妙度为 2+(-6)+8=4。
最优方案为：乐曲由和弦 1,3,5 组成，美妙度为 5+2+4=11。
所有数据满足：-1000 \leq A_i \leq 1000，1 \leq L \leq R \leq n 且保证一定存在满足要求的乐曲。
WA5:样例已过
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAX_N=500010;
ll mx[MAX_N][21],cnt[MAX_N];
ll n,k,x,y,ans=0;
void rmq(){
for(ll i=1;i<=n;i++)mx[i][0]=i;
for(ll j=1;(1<<j)<=n;j++){
for(ll i=1;i+(1<<j)-1<=n;i++){
if(cnt[mx[i][j-1]]>cnt[mx[i+(1<<(j-1))][j-1]])mx[i][j]=mx[i][j-1];
else mx[i][j]=mx[i+(1<<(j-1))][j-1];
}
}
return;
}
ll que(ll l,ll r){
ll Qlen=log2(r-l+1);
if(cnt[mx[l][Qlen]]>cnt[mx[r-(1<<Qlen)+1][Qlen]])return mx[l][Qlen];
else return mx[r-(1<<Qlen)+1][Qlen];
}
typedef struct node{
int a,b,c,d;
node(){}
node(ll a,ll b,ll c):a(a),b(b),c(d),d(que(b,c)){}
friend bool operator < (const node& a,const node& b){
return cnt[a.d]-cnt[a.a-1]<cnt[b.d]-cnt[b.a-1];
}
}node;
priority_queue<node> q;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>k>>x>>y;
//cout<<k<<x<<y<<endl;
for(ll i=1;i<=n;i++){
cin>>cnt[i];
cnt[i]+=cnt[i-1];
}
rmq();
for(ll i=1;i<=n;i++){
//cout<<i+x-1<<endl;
if(i+x-1<=n)q.push(node(i,i+x-1,min(i+y-1,n)));
//cout<<i+y-1<<endl;
}
ans=0;
while(k--){
ll a=q.top().a,b=q.top().b,c=q.top().c,d=q.top().d;
q.pop();
ans+=cnt[d]-cnt[a-1];
//cout<<cnt[d]<<' '<<d<<endl;
if(b!=d)q.push(node(a,b,d-1));
if(d!=c)q.push(node(a,d+1,c));
}
cout<<ans;
return 0;
}