题解 P2048 【[NOI2010]超级钢琴】
whyl
2019-10-01 18:55:32
我要解出一个
i l r x v的 组
我可以查找的是一个最大值
并且我要知道他在哪个位置
查最大值ST表即可
但是查找位置的话
st表是不是也可以直接维护处位置来
答案是肯定的
只要开一个数组记录（一个2的j次方的最大值）
在哪一个位置即可
贪心每次取出最大的并将最大的分裂成为
i l x-1 posl vl
i x+1 r pos2 vr
即可
最后不要忘记要开long long
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x=0,f=1;
char p=getchar();
while(!isdigit(p)){
if(p=='-') f=-1;
p=getchar();
}
while(isdigit(p)) x=(x<<3)+(x<<1)+p-48,p=getchar();
return x*f;
}
const int maxn=5e5+5;
struct node{
int start,l,r,val,pos;
bool operator <(const node x)const{
return x.val>val;
}
};
int f[maxn][21],p[maxn][21],n,m,L,R,ans,x[maxn],sum[maxn];
priority_queue<node> q;
inline void pre_work(){
for(int j=1;j<=19;j++)
for(int i=1;i+(1<<j)-1<=n;i++){
if(f[i][j-1]<f[i+(1<<j-1)][j-1]){
f[i][j]=f[i+(1<<j-1)][j-1];
p[i][j]=p[i+(1<<j-1)][j-1];
}
else{
f[i][j]=f[i][j-1];
p[i][j]=p[i][j-1];
}
}
}
inline pair<int,int> query(int l,int r){
int t=log2(r-l+1);
pair<int,int> pi;
if(f[l][t]<f[r-(1<<t)+1][t]){
pi.first=f[r-(1<<t)+1][t];
pi.second=p[r-(1<<t)+1][t];
}
else{
pi.first=f[l][t];
pi.second=p[l][t];
}
return pi;
}
signed main(){
n=read();m=read();L=read();R=read();
for(int i=1;i<=n;i++) x[i]=read(),p[i][0]=i;
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+x[i];
for(int i=1;i<=n;i++) f[i][0]=sum[i];
pre_work();
for(int i=1;i<=n;i++){
if(i+L-1<=n){
int l=i+L-1,r=min(i+R-1,n);
pair<int,int> pi=query(l,r);
q.push((node){i,l,r,pi.first-sum[i-1],pi.second});
}
else break;
}
// cout<<"%^&"<<endl;
while(m--){
// cout<<ans<<endl;
node a=q.top();
q.pop();
ans+=a.val;
if(a.pos==a.l){
// cout<<"$%^"<<endl;
if(a.l==a.r) continue;
pair<int,int> pi=query(a.l+1,a.r);
// cout<<":"<<endl;
q.push((node){a.start,a.l+1,a.r,pi.first-sum[a.start-1],pi.second});
}
else if(a.pos==a.r){
if(a.l==a.r) continue;
pair<int,int> pi=query(a.l,a.r-1);
q.push((node){a.start,a.l,a.r-1,pi.first-sum[a.start-1],pi.second});
}
else{
pair<int,int> pi=query(a.l,a.pos-1);
q.push((node){a.start,a.l,a.pos-1,pi.first-sum[a.start-1],pi.second});
pi=query(a.pos+1,a.r);
q.push((node){a.start,a.pos+1,a.r,pi.first-sum[a.start-1],pi.second});
}
}
cout<<ans<<endl;
return 0;
}
```