P2048 [NOI2010]超级钢琴(RMQ+堆+贪心)
2024-09-23 14:34:34
区间和--->前缀和做差
多次查询区间和最大--->前缀和RMQ
每次取出最大的区间和--->堆
于是我们设个3元组$(o,l,r)$,表示左端点为$o$,右端点在$l,r$之间(最优处为$t$)的最大区间和。
$t$可以RMQ在$l,r$间$O(1)$查询
所以我们事先把$n$个三元组(1<=o<=n)扔到堆里,每次把$s[t]-s[o-1]$最大的拿出来累加进答案。
取出来后$[o,t]$就不能取了,于是我们再把$(o,l,t-1)$和$(o,t+1,r)$再扔进堆里就好辣
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define rint register int
using namespace std;
inline int Min(int a,int b){return a<b?a:b;}
void read(int &x){
char c=getchar();x=; bool f=;
while(c<''||c>'') f=f&&(c!='-'),c=getchar();
while(''<=c&&c<='') x=x*+(c^),c=getchar();
x=f?x:-x;
}
#define N 500005
int n,k,s[N],f[][N],Log[N],a,L,R; long long ans;
void maketb(){//RMQ:f数组存的是最大值的下标
for(rint i=;i<=n;++i) f[][i]=i;
for(rint j=;(<<j)<=n;++j)
for(rint i=;i+(<<(j-))<=n;++i){
if(s[f[j-][i]]>s[f[j-][i+(<<(j-))]])
f[j][i]=f[j-][i];
else f[j][i]=f[j-][i+(<<(j-))];
}
}
int ask(int l,int r){
int k=Log[r-l+];
if(s[f[k][l]]>s[f[k][r-(<<k)+]]) return f[k][l];
else return f[k][r-(<<k)+];
}
struct data{
int o,l,r,t;
data(int A,int B,int C):
o(A),l(B),r(C),t(ask(B,C))
{}
bool operator < (const data &tmp) const{
return s[t]-s[o-]<s[tmp.t]-s[tmp.o-];
}
};priority_queue <data> h;
int main(){
read(n);read(k);read(L);read(R); Log[]=-;
for(rint i=;i<=n;++i) read(a),s[i]=s[i-]+a,Log[i]=Log[i>>]+;
maketb();
for(rint i=;i+L-<=n;++i) h.push(data(i,i+L-,Min(i+R-,n)));
while(k--){
data x=h.top(); h.pop();
ans+=s[x.t]-s[x.o-];
if(x.l<x.t) h.push(data(x.o,x.l,x.t-));
if(x.r>x.t) h.push(data(x.o,x.t+,x.r));
}printf("%lld",ans);
return ;
}
最新文章
- 批处理将字符串输出到Windows剪贴板
- WebClient 访问https
- this web application instance has been stopped already解决办法
- 设计模式之观察者(Observer)模式 代码详解
- abp zero sample
- Mysql锁机制--间隙锁的危害
- 【BZOJ3996】[TJOI2015]线性代数(最小割)
- JavaJ2EE相关知识整理
- day52 js--- bom dom
- 使用htpasswd实现Nginx验证访问
- 使用CDN做网站的内容加速
- react-router 4 路由的嵌套
- spring中注册bean(通过代码动态注册)
- Netty In Action中文版 - 第三章:Netty核心概念
- MVC笔记 Controller相关技术
- 中间件——Oracle Fusion Middleware
- Setting up an OpenGL development environment in ubuntu
- ajax 全局拦载处理,可加密、过滤、筛选、sql防注入处理
- Windows Server2008服务器可以远程桌面,但在内网中却Ping不通--解决方法
- [Bzoj3991]寻宝游戏(dfs序+set)
热门文章
- 正则表达式匹配域名、网址、url
- 收集:C# WinForm获取当前路径汇总
- 问题:mysql服务正在启动 mysql服务无法启动 &;&; mysql启动脚本 mysql关闭脚本
- SqlServer表和EXCEL数据互相复制方法
- HTML5表单及其验证
- 并查集(disjoint)
- talend openstudio 在OracleInput组件中guess Schema 出现Database connection is failed 的错误
- IFrame session(转)
- Introduction to debugging neural networks
- Acperience (英语阅读 + 数学推导)