[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;
}

  

最新文章

  1. Python多线程爬虫爬取电影天堂资源
  2. .net MVC中异常日志
  3. jdbcTemplate之jdbc模板技术
  4. Java中的char到底是多少个字节?
  5. Shell编程中括号判断中赋值语句和判断语句
  6. ActiveMQ第四弹:在HermesJMS中创建ActiveMQ Session
  7. AngularJS开发指南3:Angular主要组成部分以及如何协同工作
  8. Android Packaging Problem
  9. Code Sign error: No unexpired provisioning profiles found that contain any of the keychain&#39;s signing certificates
  10. Ubuntu 下一个可用的音乐播放器
  11. MySQL Server类型之MySQL客户端工具的下载、安装和使用
  12. JS数组方法总结
  13. Redis Sentinel中的机制与原理详解
  14. eShopOnContainers 知多少[3]:Identity microservice
  15. s:if 判断 s:property
  16. AI学习---数据IO操作&amp;神经网络基础
  17. Jtest的简单使用
  18. TMS320VC5509驱动LCD1602
  19. JVM学习十三:JVM之堆分析
  20. java的值传递机制

热门文章

  1. HandlerMapping执行过程。。。
  2. JAVA基础之项目分包
  3. mongodb关联查询 和spring data mongodb
  4. str中的join方法,fromkeys(),set集合,深浅拷贝(重点)
  5. Bibtex使用介绍
  6. $&#39;\r&#39;: command not found 或者 syntax error: unexpected end of file 或者 syntax error near unexpected token `$&#39;\r&#39;&#39;
  7. python基础教程总结15——6 CGI远程编辑
  8. 什么样子的WordPress网站更受搜索引擎欢迎
  9. CPP-网络/通信:SSL功能和原理
  10. Java 从资源文件(.properties)中读取数据