自动搬运

查看原文

来自洛谷，原作者为

	Demeanor_Roy 小时候我们总想去改变别人，后来发现，比起改变，筛选是性价比更高的事。

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

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

以下是正文

原题链接

不错的题，这里提供一个树状数组写法。

首先对于序列每一个位置，求出 $L_i,R_i$ 分别表示以 $i$ 位置为结尾，为开始的最长不下降子序列，求法就是正着做一遍朴素的最长不下降子序列，反着做一遍最长不上升子序列，注意用 $n \log n$ 做法。

接着考虑拼接。

首先我们可以得出一个结论：改变 $k$ 个数一定比改变更少的数优秀。这很显然，因为我们可以把改成和原来相同也看作改变。

那接下来就好做了，我们对每一个位置 $i$ ，贪心地考虑它前面 $k$ 个数被改成与它相同，那只需要找一个 $j$ 属于 $[1,i-k-1]$ ，使得 $val_j \leq val_i$ 且 $L_j$ 最大，然后用 $L_j + k + R_i$ 更新答案就行了。

温馨提示：因为要用三个树状数组，最好把树状数组写成类更方便。

update on 11.19: 之前有一点没有说清楚，其实这个做法隐含了一个贪心，那就是如果改变 $[L,R]$ 这 $k$ 个数，我们只考虑其去配合以 $R+1$ 为左端点的最长不降序列，因为就算它配合以更后面的数 $x$ 为左端点的最长不降序列有更优答案，那它也不会比枚举改变 $[x-k,x-1]$ 这 $k$ 个数时去配合 $x$ 更优，因为那时 $L_j$ 选择更广。所以改变 $[L,R]$ 这 $k$ 个数时，自然是改变成 $val_{R+1}$ 更优。

update on 11.25: 代码有一点小锅，已修。

update on 2025.5.12: 代码又有一点小锅，已修。

下附代码：

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
int n,k,ans,val[N],L[N],R[N];
vector<int> vec;
struct BIT
{
	int C[N];
	inline void add(int x,int y){for(;x<=n+1;x+=x&-x)	C[x]=max(C[x],y);}
	inline int query(int x)
	{
		int ans=0;
		for(;x;x-=x&-x)	ans=max(ans,C[x]);
		return ans;
	}
}le,re,s;
int main()
{
	scanf("%d%d",&n,&k);
	val[0]=1;val[n+1]=n+1;
	for(int i=1;i<=n;i++)	scanf("%d",&val[i]);
	for(int i=1;i<=n;i++)	vec.push_back(val[i]);
	sort(vec.begin(),vec.end());
	vec.erase(unique(vec.begin(),vec.end()),vec.end());
	for(int i=1;i<=n;i++)	val[i]=lower_bound(vec.begin(),vec.end(),val[i])-vec.begin()+1;
	for(int i=1;i<=n;i++)
	{
		L[i]=le.query(val[i])+1;
		le.add(val[i],L[i]);
	}
	for(int i=n;i>=1;i--)
	{
		R[i]=re.query(n-val[i]+1)+1;
		re.add(n-val[i]+1,R[i]);
	}
	for(int i=k+1;i<=n+1;i++)
	{
		s.add(val[i-k-1],L[i-k-1]);
		ans=max(ans,s.query(val[i])+k+R[i]);
	}	
	printf("%d",ans);
	return 0;	
} 

完结撒花~