CF1468A

设 \(f_i\) 表示以第 \(i\) 个结尾，强制选第 \(i\) 个所能得到的最长几乎上升序列的长度。

则 \(f_i=\max\limits_{j\lt i,a_j\le a_i}\left\{f_j+1+w(i,j)\right\}\)。

其中 \(w(i,j)=0/1\) 表示 \([j+1,i-1]\) 有没有比 \(a_i\) 和 \(a_j\) 都大的数。

对于每个 \(i\) 用单调栈预处理出 \(pre_i\) 表示 \(i\) 左边第一个大于 \(a_i\) 的位置，没有则为 \(0\)。

则 \(f_i=\max(\max\limits_{j\lt pre_i,a_j\le a_i}\left\{f_j\right\}+2,\max\limits_{pre_i\le j\lt i,a_j\le a_i}\left\{f_j\right\}+1)\)。

将 \(a\) 从小到大排序后依次加入，发现涉及到的操作有求前缀 \(\max\)，单点修改，用树状数组维护即可。

具体细节看代码。

Code：

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair <int, int> pii;
const int N = 500005;
int T;
int n;
pii a[N]; int stk[N], top;
int f[N], pre[N];
int c[N];

void upd(int x, int y) { for (; x <= n; x += x & -x) c[x] = max(c[x], y); }
int query(int x) { int res = 0; for (; x; x -= x & -x) res = max(res, c[x]); return res; }

void solve() {
	scanf("%d", &n);
	memset(c + 1, 0, sizeof (int) * n);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i].fi), a[i].se = i;
	top = 0;
	for (int i = 1; i <= n; ++i) {
		while (top && a[stk[top]] <= a[i]) --top;
		pre[i] = stk[top], stk[++top] = i;
	}
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; ++i) {
		int _ = a[i].se;
		f[_] = query(_ - 1) + 1;
		if (pre[_]) f[_] = max(f[_], query(pre[_] - 1) + 2);
		upd(_, f[_]);
	}
	printf("%d\n", query(n));
}

int main() {
	scanf("%d", &T);
	while (T--) solve();
	return 0;
}

原文地址：http://www.cnblogs.com/Kobe303/p/16798814.html