这题考转换问题啊

假如区间[l,r]+1，不如[l,n]+1

假如区间[l,r]-1，不如[1,r]-1，就变成(r,n]+1

问题就转化成了求LIS，其中x~n一段可以加m

正着跑维护1~x-1的最长上升，且x必选并+m的最大值

反着跑维护x~n的最长上升，两个合并一下

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int a[210000],f[210000],h[210000];int tp,g[210000];int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]); tp=1; memset(g,63,sizeof(g)); f[1]=1,g[1]=a[1]; for(int i=2;i<=n;i++) { if(a[i]>g[tp]) { tp++; f[i]=tp; g[tp]=a[i]; } else if(a[i]+m>g[tp]) { f[i]=tp+1; int id=lower_bound(g+1,g+tp+1,a[i])-g; g[id]=a[i]; } else { int id=lower_bound(g+1,g+tp+1,a[i])-g; f[i]=lower_bound(g+1,g+tp+1,a[i]+m)-g; g[id]=a[i]; } } int ans=tp;tp=1; memset(g,63,sizeof(g)); h[n]=1,g[1]=-a[n]; ans=max(ans,f[n]+h[n]-1); for(int i=n-1;i>=1;i--) { if(-a[i]>g[tp]) { tp++; h[i]=tp; g[tp]=-a[i]; } else { int id=lower_bound(g+1,g+tp+1,-a[i])-g; h[i]=id; g[id]=-a[i]; } ans=max(ans,f[i]+h[i]-1); } printf("%d\n",ans); return 0;}