Code Level : ※
Thingking Level: ※※

Description

$给定长度为 n 的序列 a_n 和 x ,可以给一个连续的区间加 \ d \ (d \in [-x,x])$ $求最长LIS长度$

Solution

这题唯一的思维难度是它的小 trick

对于一个数，我们给它加上负值是无意义的，因为这等同于我们给其后的区间整体加上它的相反数

而进一步可得，我们只需要考虑加上值对其前面的贡献。而考虑最大值，即直接加上d

Details

对于求最长LIS，考虑以一个单调栈来存储我们选择的序列：

那么，对于新加入的元素 x 和当前栈顶元素 y，考虑以 x 为尾的 LIS

如果 (x>y) 直接将 x 加入栈尾，此时以 x 为尾的 LIS 长度为栈的大小

否则以 x 尾的 LIS长度即为以栈中第一个大于等于x的 p 的为尾的 LIS 长度。根据贪心，我们可以用x去更新p，因为x<=p

对于处理最终答案，我们只需考虑当前值加上x(x为能取得最大值)，其前能得到得 LIS 长度（上面所讲），和其后的值给x的贡献（即以x为头的LIS）

Code

#include<bits/stdc++.h>
using namespace std;
const int nn=200005;
int i,p,n,x,s[nn],a[nn],b[nn],q[nn],t=0,ans=0;
int main(){
    scanf("%d%d",&n,&x); x=abs(x);
    for(i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=-a[i];
    q[++t]=b[n];
    for(i=n-1;i>0;i--)
    if(q[t]<b[i]) s[i]=t,q[++t]=b[i];
    else { p=lower_bound(q+1,q+1+t,b[i])-q; s[i]=p-1; q[p]=b[i];}
    t=0; q[++t]=a[1];
    for(i=2;i<=n;i++){
        if(a[i]+x>q[t]) ans=max(ans,t+s[i]+1);
        else {
            p=lower_bound(q+1,q+1+t,a[i]+x)-q;
            ans=max(ans,p+s[i]); 
        }
        if(a[i]>q[t]) q[++t]=a[i];
        else {
            p=lower_bound(q+1,q+1+t,a[i])-q;
            q[p]=a[i];
        }
    } printf("%d\n",ans);
    return 0;   
}