题意：
给出一个长度为$n$的序列${a_n}$。
已知一个正整数$x$，你有一次机会指定区间$[l,r]$，令$forall iin [l,r],;a_i=a_i+d\,(|d|le x)$。
求最大化的最长上升子序列的长度。
$1 le n le 2 imes 10^5 , quad 1 le a_i,x le 10^9$且均为正整数。
分析：
可以很容易发现三个性质：
性质一：抬升$[l,r]$不优于抬升$[l,n]$，降低$[l,r]$不优于降低$[1,l]$。
性质二：降低$[1,p]$等价于抬升$[p+1,n]$。
性质三：抬升/降低$k$不优于抬升/降低$x$。
由此很容易想到分成两块求部分答案，再拼成总答案。
但这并不是简单地把向左/右拓展的上升子序列或者它们的前/后缀最大值在某个分割点加起来。怎么办呢？
考虑在从左向右做$LIS$时加上一些限制，即$a_i$必须不超过$mathop{min} limits _{j=i+1} ^n { a_j }$才能加入$LIS$中。
这个做法显然是错误的，因为这样会遗漏很多贡献。如果坚持用“限制法”来做，那么$i$每移动一次，限制更新了，都要把之前的全部重算一次，这样才能正确。
等一下，是我们的思路出了问题吗？有这么复杂吗？
让我们冷静一下，现在我们在求什么?
一些“左拼图”候选。
“限制法”尝试让现在求得的“左拼图”能对上所有“右拼图”，这是不现实的。
所以我们应该考虑的是怎么样让对应长度的“拼图”“契合”。应该让$a_i$到左侧的$LIS$中去找到位置。
来一个规范一点的定义：
设$f_i$表示将$[1,i-1]$降低时，以$a_i$为结尾的最长上升子序列长度。
那么我们正着做$LIS$时把每个$a_i-x$放入单调数组里，当$2le ile n$时$a_i$在单调数组里的合法位置就是$f_i$了。
之后再反着做$LIS$，设单调数组在$i$时的长度为$l_i$，那么答案是$max { \, mathop{max}limits^{n}_{i=2}{ f_i + l_i } \, , \, l_1 \, }$。
实现（100分）：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define IL inline using namespace std; const int N=2e5; const int inf=0x3f3f3f3f; int n,x,a[N+3]; int f[N+3]; IL bool cmp1(int p,int q){ return p>=q; } IL bool cmp2(int p,int q){ return p<=q; } IL int bins(int *a,int l,int r,int x,bool cmp(int p,int q)){ int mid,ans=0; while(l<=r){ mid=(l+r)>>1; if(cmp(a[mid],x)){ ans=mid; r=mid-1; } else l=mid+1; } return ans; } int main(){ freopen("glo.in","r",stdin); freopen("glo.out","w",stdout); scanf("%d%d",&n,&x); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int s[N+3],k; memset(s,0x3f,sizeof s); s[0]=-inf; k=0; for(int i=1;i<=n;i++){ f[i]=max(0,bins(s,1,k+1,a[i],cmp1)-1); int p=bins(s,1,k+1,a[i]-x,cmp1); s[p]=a[i]-x; k=max(k,p); } int ans; memset(s,0,sizeof s); s[0]=inf; k=ans=0; for(int i=n;i>=1;i--){ int p=bins(s,1,k+1,a[i],cmp2); s[p]=a[i]; k=max(k,p); ans=max(ans,p+f[i]); } printf("%d",ans); return 0; }
小结：
显然性质$
ightarrow$化归拆解问题$
ightarrow$合适地拼出答案。