自动搬运

查看原文

来自洛谷，原作者为

	DaiRuiChen007 白鸟白鸟 不要回头望 你要替我飞去那地方 一去那地方 那是你我共同故乡

搬运于2025-08-24 23:04:17，当前版本为作者最后更新于2024-08-19 10:28:43，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Problem Link

题目大意

给定 $n$ 阶排列 $p$，分成两个子序列 $q,r$，最大化 $q$ 中 Local-Max 个数加上 $r$ 中 Local-Min 个数。

数据范围：$n\le 2\times 10^5$。

思路分析

考虑 $q,r$ 第一次值域相交的时刻 $a_i$，那么在 $(i,n]$ 范围内可以直接取 LIS 和 LDS，其他元素可以直接放到对面的序列里，不影响对面的 Local-Max 或 Local-Min。

在 $a_i$ 之前，$q$ 一定取 $<a_i$ 所有数，$r$ 一定取 $>a_i$ 所有数，可以用 std::set 对每个 $x$ 维护 $a_i=x$ 时当前 $q,r$ 对应的权值和。

然后枚举 $a_i$ 属于 $q/r$，如果属于 $q$，那么就取 $a(i,n]$ 中值域 $<\min r[1,i)$ 和 $>\min r[1,i)$ 的 LIS 和 LDS，倒序扫描线，树状数组维护。

时间复杂度 $\mathcal O(n\log n)$。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int n,a[MAXN],pre[MAXN],suf[MAXN],f[MAXN],w[MAXN];
struct FenwickTree1 {
	int tr[MAXN],s;
	void init() { fill(tr,tr+n+1,0); }
	void add(int x,int v) { for(;x<=n;x+=x&-x) tr[x]=max(tr[x],v); }
	int qry(int x) { for(s=0,x=min(x,n);x;x&=x-1) s=max(s,tr[x]); return s; }
}	T1;
struct FenwickTree2 {
	int tr[MAXN],s;
	void init() { fill(tr,tr+n+1,0); }
	void add(int x,int v) { for(;x;x&=x-1) tr[x]=max(tr[x],v); }
	int qry(int x) { for(s=0,x=max(x,1);x<=n;x+=x&-x) s=max(s,tr[x]); return s; }
}	T2;
void solve() {
	scanf("%d",&n); int ans=0;
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	set <int> S{0,n+1}; f[0]=f[n+1]=0;
	for(int i=1;i<=n;++i) {
		auto it=--S.upper_bound(a[i]);
		w[i]=f[a[i]]=++f[*it],pre[i]=*it,suf[i]=*++it,S.insert(a[i]);
	}
	T1.init(),T2.init();
	for(int i=n;i>=1;--i) {
		ans=max(ans,w[i]+T1.qry(pre[i])+T2.qry(pre[i]));
		ans=max(ans,w[i]+T1.qry(suf[i])+T2.qry(suf[i]));
		T1.add(a[i],T1.qry(a[i])+1),T2.add(a[i],T2.qry(a[i])+1);
	}
	printf("%d\n",ans);
}
signed main() {
	int Q; scanf("%d",&Q);
	while(Q--) solve();
	return 0;
}