题解：P11187 配对序列

这是一篇树状数组优化 DP 的题解。

有显然 DP：设 $f(i, 0/1)$ 表示只考虑前 $i$ 个数，且第 $i$ 个数一定被划分到了子序列中，且 $i$ 是在这个子序列的奇数还是偶数位置的方案数。

转移可以枚举子序列中倒数第二个元素的位置：

$$
f(i, 0) = 1 + \sum_{j=1}^{i-1} [a_j = a_i] f(j, 1) \\
f(i, 1) = 1 + \sum_{j=1}^{i-1} [a_j \ne a_i] f(j, 0)
$$

直接做是 $\mathcal O(n^2)$ 的。

考虑优化转移。若我们动态维护 $w_{0, k} = \sum_{j=1}^{i-1} [a_i=k] f(i, 0),w_{1, k} = \sum_{j=1}^{i-1} [a_i=k] f(i, 1)$，那么转移可以优化成：

$$
f(i, 0) = 1 + w_{1, a_i} \\
f(i, 1) = 1 + \max_{j \ne a_i} w_{0, j}
$$

$f(i, 0)$ 的转移就可以做到 $\mathcal O(1)$ 了。但是 $f(i, 1)$ 的转移不能。

像这种在全集中只删除一个数的转移可以考虑维护其前后缀。即我们令 $pre_j = \max_{k=1}^j w_{0, j},suf_j = \max_{k=j}^{V} w_{0, j}$（其中 $V$ 是值域，取 $V = 5 \times 10^5$）。那么：

$$
f(i, 1) = 1 + \max(pre_{a_i-1}, suf_{a_i+1})
$$

这样也能做到 $\mathcal O(1)$ 转移了。

现在的问题是如何快速维护 $w_{0,i},w_{1,i},pre_i,suf_i$。前二者是极易的，而后者只是前者的前缀/后缀最大值，树状数组维护即可。

```cpp
#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 10;

int n, a[N], f[N][2];

struct BIT {
	int tr[N];
	
	void modify(int u, int x) {
		for (int i = u; i <= 5e5; i += i & -i) tr[i] = max(tr[i], x);
	}
	
	int query(int u) {
		int res = 0;
		for (int i = u; i; i -= i & -i) res = max(res, tr[i]);
		return res;
	}
}T1, T2;

int mx[N];

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++ i ) cin >> a[i];
	for (int i = 1; i <= n; ++ i ) {
		f[i][0] = mx[a[i]] ? mx[a[i]] + 1 : 0;
		f[i][1] = max(T1.query(a[i] - 1), T2.query(5e5 - a[i])) + 1;
		
		mx[a[i]] = max(mx[a[i]], f[i][1]);
		T1.modify(a[i], f[i][0]);
		T2.modify(5e5 - a[i] + 1, f[i][0]);
	}
	int res = 0;
	for (int i = 1; i <= n; ++ i ) res = max(res, f[i][0]);
	cout << res;
	return 0;
}
```

正在渲染内容...