BZOJ 5442: [Ceoi2018]Global warming
2024-09-02 12:21:08
[l,r]+x不如[l,n]+x
[l,r]-x不如(r,n)+x
所以等价于只有[l,n]+x
枚举断点树状数组合并
难度在于想到这个贪心
#include<cstdio>
#include<algorithm>
using namespace std;
int cnt,n,x,A[1000005],stack[1000005],F[1000005],E[1000005],S[1000005],T[1000005],a[1000005],tree[1000005];
void solve(){
int tail=0;
stack[0]=-1e9;
for (int i=1; i<=n; i++){
if (A[i]>stack[tail]) {
stack[++tail]=A[i];
F[i]=tail;
}
else{
int ID=lower_bound(stack+1,stack+tail+1,A[i])-stack;
stack[ID]=A[i];
F[i]=ID;
}
}
}
int lowbit(int x){
return x&(-x);
}
void insert(int x,int y){
for (int i=x; i<=cnt; i+=lowbit(i)) tree[i]=max(tree[i],y);
}
int query(int x){
int ans=0;
for (int i=x; i; i-=lowbit(i)) ans=max(ans,tree[i]);
return ans;
}
int main(){
scanf("%d%d",&n,&x);
if (x<0) x=-x;
for (int i=1; i<=n; i++) scanf("%d",&a[i]);
for (int i=1; i<=n; i++) E[++cnt]=a[i];
for (int i=1; i<=n; i++) E[++cnt]=a[i]+x-1;
sort(E+1,E+cnt+1);
cnt=unique(E+1,E+cnt+1)-E-1;
for (int i=1; i<=n; i++) A[i]=a[i];
solve();
for (int i=1; i<=n; i++) S[i]=F[i];
for (int i=1; i<=n/2; i++) swap(A[i],A[n-i+1]);
for (int i=1; i<=n; i++) A[i]=-A[i];
solve();
for (int i=1; i<=n; i++) T[i]=F[n-i+1];
int ans=0;
for (int i=1; i<=n; i++){
ans=max(ans,T[i]+query(lower_bound(E+1,E+cnt+1,a[i]+x-1)-E));
insert(lower_bound(E+1,E+cnt+1,a[i])-E,S[i]);
}
printf("%d\n",ans);
return 0;
}
最新文章
- Python多线程爬虫爬取电影天堂资源
- .net MVC中异常日志
- jdbcTemplate之jdbc模板技术
- Java中的char到底是多少个字节?
- Shell编程中括号判断中赋值语句和判断语句
- ActiveMQ第四弹:在HermesJMS中创建ActiveMQ Session
- AngularJS开发指南3:Angular主要组成部分以及如何协同工作
- Android Packaging Problem
- Code Sign error: No unexpired provisioning profiles found that contain any of the keychain&#39;s signing certificates
- Ubuntu 下一个可用的音乐播放器
- MySQL Server类型之MySQL客户端工具的下载、安装和使用
- JS数组方法总结
- Redis Sentinel中的机制与原理详解
- eShopOnContainers 知多少[3]:Identity microservice
- s:if 判断 s:property
- AI学习---数据IO操作&;神经网络基础
- Jtest的简单使用
- TMS320VC5509驱动LCD1602
- JVM学习十三:JVM之堆分析
- java的值传递机制
热门文章
- HandlerMapping执行过程。。。
- JAVA基础之项目分包
- mongodb关联查询 和spring data mongodb
- str中的join方法,fromkeys(),set集合,深浅拷贝(重点)
- Bibtex使用介绍
- $&#39;\r&#39;: command not found 或者 syntax error: unexpected end of file 或者 syntax error near unexpected token `$&#39;\r&#39;&#39;
- python基础教程总结15——6 CGI远程编辑
- 什么样子的WordPress网站更受搜索引擎欢迎
- CPP-网络/通信:SSL功能和原理
- Java 从资源文件(.properties)中读取数据