自动搬运

查看原文

来自洛谷，原作者为

	lnwhl AFO

搬运于2025-08-24 22:16:10，当前版本为作者最后更新于2022-07-16 11:54:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

目前的最优解。

Description

给定长度为 $n$ 的数组 $a$ ，你可以将任意一段区间 $[l,r]$ 中的每一个元素 $+d$，其中 $-x\le d\le x$，问一次操作后的最长上升子序列长度。

Solution

如果将 $[l,r]$ 区间内的元素都减小，可以增加 $[l,r]$ 与 $[r+1,n]$ 连接的 LIS 长度。但这有可能减小 $[l,r]$ 与 $[1,l-1]$ 这段的 LIS，所以我们可以贪心的想到，对于 $d<0$ 的情况，选择 $[1,r]$ 区间一定会比 $[l,r]$ 区间更优。

对于 $d>0$ 的情况也同理。因为区间内相对大小不变，所以不难发现将 $[i+1,n]$ 加一个值的效果和 $[1,i]$ 区间减一个值的效果是相同的，所以只需要考虑 $d<0$ 的情况。

我们进一步分析，可以发现将 $[1,i]$ 区间减的值越大一定更优。所以原问题就变成了求 $[1,i]$ 区间内的元素都减去 $x$ 后，最长上升子序列的长度最大为多少。

暴力修改 + LIS 的复杂度是 $O(n^2\log n)$ 的，需要优化。考虑到修改过后区间内部相对大小不变，可以预先求出 $[1,i]$ 区间以 $a_i$ 结尾的 LIS 长度，为 $L_i$，设修改过后 $[i,n]$ 区间以 $a_i$ 开头的 LIS 长度为 $R_i$，答案即为 $\max\limits_{i=1}^nL_i+R_i-1$。复杂度是 $O(n\log n)$ 的，轻松最优解。

当然，你也可以离散化后用树状数组求最大值，复杂度不变，只是代码复杂一些，欢迎读者思考。

Code

#include <bits/stdc++.h>
#define Rint register int
using namespace std;
const int N=2e5+5;
int n,x,a[N],lis[N],L[N],R[N],ans;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x*f;
}
int main()
{
	n=read(),x=read();
	for(Rint i=1;i<=n;++i)a[i]=read();
	memset(lis,0x7f,sizeof(lis));
	for(Rint i=1;i<=n;++i)
	{
		int j=lower_bound(lis,lis+n,a[i])-lis;
		lis[j]=a[i];L[i]=j+1;ans=max(ans,L[i]);
	}
	memset(lis,0x7f,sizeof(lis));
	for(Rint i=n;i>=1;--i)
	{
		int j=lower_bound(lis,lis+n,-a[i]+x)-lis;
		int jj=lower_bound(lis,lis+n,-a[i])-lis;
		lis[jj]=-a[i];ans=max(ans,L[i]+j);
	}
	printf("%d",ans);
	return 0;
}