题解：P8776 [蓝桥杯 2022 省 A] 最长不下降子序列

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,a[N],k,dp[N],pd[N],t[N],ans=0;
int lowbit(int x)//树状数组 
{
	return x&(-x);//lowbit不过多解释不知道的可以去度娘看看 
}
void up(int x,int v);//维护x节点的最大值 修改x的值 
int q(int x);//维护最长不下降子序列 
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		dp[i]=1;
		pd[i]=1;//初始化 
	}
	for(int i=0;i<N;i++)t[i]=1;
	dp[1]=1;
	pd[n]=1;
	for(int i=2;i<=n;i++)//求从1到i的最长不下降子序列 
	{
		dp[i]=q(a[i]);//找前缀最大值 
		up(a[i],dp[i]+1);//更新树状数组 
	} 

	for(int i=0;i<N;i++)t[i]=1;//初始化 
	for(int i=n-1;i>=1;i--)//求从i到n的最长不下降子序列 
	{
		pd[i]=q(N-a[i]);//因为要从右向左找 但是树状数组的逻辑默认是从小到大维护值的所以要取反 
		up(N-a[i],pd[i]+1);//更新树状数组 
	}
	for(int i=1;i<=n;i++)
	{
		ans=max(ans,dp[i]+k+pd[i]-1);//枚举节点找最优 
	}
	cout<<min(ans,n)<<"\n";
	return 0;
}
int q(int x)//
{
	int ans=0;//初始化最大值为0 
	while(x>0)//从x开始向下遍历 
	{
		ans=max(ans,t[x]);//更新当前区间的最大值 
		x-=lowbit(x);//移动到左边的节点 
	}
	return ans;
}
void up(int x,int v)//维护x节点的最大值 
{
	while(x<=N)//从位置x开始，向上更新树状数组
	{
		t[x]=max(t[x],v);// 更新当前节点为最大值
		x+=lowbit(x);// 移动到父节点 
	}
	return ;
}