菜王的 blog

不需分析结论的麻烦做法，模拟赛时想到这个做法没写出来，跟同学说场上没写出这个题的时候同学大为震惊……

首先，可以想到设 $f'_{i, j}$ 为最后一个元素为 $i$，选了 $j + 1$ 个是否可行。转移方程即为

$\begin{cases} f'_{i, j} \gets f_{k, j - 1} \ (j = \texttt{"U"},a_i > a_k)\\ f'_{i, j} \gets f_{k, j - 1} \ (j = \texttt{"D"},a_i < a_k)\\ \end{cases}$

这个转移显然可以用前缀或优化，我们设 $f_{i, j, k}$ 为 $\bigvee_{x \le i, a_x < k} f'_{x, j}$，类似的设 $g_{i, j, k}$ 为 $\bigvee_{x \le i, a_x > k} f'_{x, j}$。

首先可以滚掉第一维 $k$。即变为 $f_{j, k}, g_{j, k}$ 这样的形式；然后可以舍弃原数组。具体来说，$f'_{i, j}$ 就等于 $f_{j - 1, a_i}$ 或者 $g_{j - 1, a_i}$，所以可以对于 $k > a_i$ 的所有 $f_{j, k}$ 以及 $k < a_i$ 的所有 $g_{j, k}$ 更新过去，不需再用原数组。转移方程变为

$\begin{cases} f_{j, k} \gets f_{j - 1, a_i} \ (j = \texttt{"U"},k > a_i)\\ g_{j, k} \gets f_{j - 1, a_i} \ (j = \texttt{"U"},k < a_i)\\ f_{j, k} \gets g_{j - 1, a_i} \ (j = \texttt{"D"},k > a_i)\\ g_{j, k} \gets g_{j - 1, a_i} \ (j = \texttt{"D"},k < a_i)\\ \end{cases}$

现在转移还是需要 $O(n)$，而且现在需要维护的状态是一个 $01$ 数组，这很不好。继续发现，因为 $f$ 前缀或的性质，所以对于每个 $j$，一定可以找到一个断点 $pf_j$（$1 \le pf_j \le n$） 满足对于所有 $k \le pf_j$ 的 $k$，都有 $f_{k, j} = 0$；对于所有 $k > pf_j$ 的 $k$，都有 $f_{k, j} = 1$。对于 $g$ 也可以类似的找到 $pg_j$。

我们只需要维护这些断点，就可以 $O(1)$ 找出对应的 $f$ 值和 $g$ 值。而且，我们还可以发现，对于一个有效转移（即转移过去的值为 $1$），就相当于给对应的断点取了一个 $\min / \max$。于是可以写出转移方程：

$\begin{cases} pf_j \overset{\min}{\gets} a_i, pg_j \overset{\max}{\gets} a_i \ (j = \texttt{"U"},pf_{j - 1} < a_i)\\ pf_j \overset{\min}{\gets} a_i, pg_j \overset{\max}{\gets} a_i \ (j = \texttt{"D"},pg_{j - 1} > a_i)\\ \end{cases}$

现在时间复杂度被优化到了 $O(n^2)$，而需要维护的状态数已经变为了 $O(n)$ 级别，距离目标已经很近了。

我们猜测，$pf, pg$ 这两个断点序列都是单调的，但是很遗憾，这个结论是错误的。但是我们可以发现一个进阶结论：对于所有的 $b_j$ 相同的位置，$pf, pg$ 在这些位置上是单调的，也就是说，它们都是由两个单调序列拼起来的，因为在 $b$ 相同的情况下，相邻的两个位置的决策必然有一个包含另一个。

所以，能转移的 $j$ 一定是在一个前缀内且满足 $b_j$ 为某个字符的，而这个前缀也是可以快速求出的。

具体的，我们需要维护 $pf, pg$ 并支持以下操作：

• 对于一个前缀内 $b_j = ch$ 的 $j$ 令 $pf_j \overset{\min}{\gets} a_i, pg_j \overset{\max}{\gets} a_i$；
• 求出位置 $j$ 使得 $j$ 为最后一个满足 $b_{j + 1} = \texttt{"U"}$ 且 $pf_j < a_i$ 的位置；
• 求出位置 $j$ 使得 $j$ 为最后一个满足 $b_{j + 1} = \texttt{"D"}$ 且 $pg_j > a_i$ 的位置。

我们开一棵线段树，每一个节点中对于每一种二元组 $(b_j, b_{j + 1})$ 维护出区间内的 $\min pf_j, \max pg_j$ 以及标记，每次修改直接对于所有满足要求的二元组都对应的打上标记，而询问位置就在线段树上二分即可。

求答案比较简单，我们只需要倒着搜整棵线段树，找到第一个 $pf_j < n$ 或者 $pg_j > 1$ 的 $j$ 作为答案。总时间复杂度为 $O(n \log n)$，常数较大。

接下来是完整代码：

#include <algorithm>
#include <cstring>
#include <cstdio>
#define inf 0x3f3f3f3f
using namespace std;
const int N = 300001;
int n, a[N], ci[N];char b[N];
struct node{int pf[4], pg[4], cz[4], tg[4];}tr[N << 2];
inline void tmin(int& x, int y){if (x == -1) x = y;else x = min(x, y);}
inline void tmax(int& x, int y){x = max(x, y);}
inline void addtag(int u, int z, int x){if (x == -1) return;
	if (z == 0) tmin(tr[u].pf[0], x), tmin(tr[u].pf[2], x), tmin(tr[u].tg[0], x);
	if (z == 1) tmax(tr[u].pg[0], x), tmax(tr[u].pg[2], x), tmax(tr[u].tg[1], x);
	if (z == 2) tmin(tr[u].pf[1], x), tmin(tr[u].pf[3], x), tmin(tr[u].tg[2], x);
	if (z == 3) tmax(tr[u].pg[1], x), tmax(tr[u].pg[3], x), tmax(tr[u].tg[3], x);
}
inline void downtag(int u){for (int i = 0;i < 4;i ++)
	addtag(u << 1, i, tr[u].tg[i]), addtag(u << 1 | 1, i, tr[u].tg[i]), tr[u].tg[i] = -1;
}
inline void pushup(int u){
	for (int i = 0;i < 4;i ++){tr[u].pf[i] = n, tr[u].pg[i] = 0;
		if (tr[u << 1].cz[i]) tmin(tr[u].pf[i], tr[u << 1].pf[i]), tmax(tr[u].pg[i], tr[u << 1].pg[i]);
		if (tr[u << 1 | 1].cz[i]) tmin(tr[u].pf[i], tr[u << 1 | 1].pf[i]), tmax(tr[u].pg[i], tr[u << 1 | 1].pg[i]);
	}
}
void build(int u, int l, int r){memset(tr[u].tg, -1, 16);
	if (l == r){ci[l] = (b[l + 1] == 'D') << 1 | b[l] == 'D';
		memset(tr[u].pf, 0x3f, 16), memset(tr[u].pg, 0, 16);
		tr[u].pf[ci[l]] = n, tr[u].pg[ci[l]] = tr[u].cz[ci[l]] = 1;return;
	}int mid = l + r >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r), pushup(u);
	for (int i = 0;i < 4;i ++) tr[u].cz[i] = tr[u << 1].cz[i] | tr[u << 1 | 1].cz[i];
}
void update(int u, int l, int r, int p, int z, int x){
	if (r <= p) return addtag(u, z << 1, x), addtag(u, z << 1 | 1, x);
	if (l > p) return;int mid = l + r >> 1;downtag(u);
	update(u << 1, l, mid, p, z, x), update(u << 1 | 1, mid + 1, r, p, z, x), pushup(u);
}
inline int gtf(int u){int res = inf;if (tr[u].cz[0]) tmin(res, tr[u].pf[0]);if (tr[u].cz[1]) tmin(res, tr[u].pf[1]);return res;}
inline int gtg(int u){int res = 0;if (tr[u].cz[2]) tmax(res, tr[u].pg[2]);if (tr[u].cz[3]) tmax(res, tr[u].pg[3]);return res;}
int fndpos(int u, int l, int r, int x){
	if (l == r) return x > gtf(u) ? l : -1;int mid = l + r >> 1;downtag(u);
	if (gtf(u << 1 | 1) < x) return fndpos(u << 1 | 1, mid + 1, r, x);
	return fndpos(u << 1, l, mid, x);
}
int gndpos(int u, int l, int r, int x){
	if (l == r) return x < gtg(u) ? l : -1;int mid = l + r >> 1;downtag(u);
	if (gtg(u << 1 | 1) > x) return gndpos(u << 1 | 1, mid + 1, r, x);
	return gndpos(u << 1, l, mid, x);
}
int solve(int u, int l, int r){
	if (l == r) return tr[u].pf[ci[l]] < n || tr[u].pg[ci[l]] > 1 ? l : 0;
	int mid = l + r >> 1;downtag(u);
	return max(solve(u << 1, l, mid), solve(u << 1 | 1, mid + 1, r));
}
int main(){scanf("%d", &n);
	for (int i = 1;i <= n;i ++) scanf("%d", &a[i]);
	scanf("%s", b + 1), build(1, 0, n - 1);
	for (int i = 1, p0, p1;i <= n;i ++){
		p0 = fndpos(1, 0, n - 1, a[i]), p1 = gndpos(1, 0, n - 1, a[i]);
		update(1, 0, n - 1, p0 + 1, 0, a[i]);
		update(1, 0, n - 1, p1 + 1, 1, a[i]);
	}printf("%d", solve(1, 0, n - 1));
}

虽然这个做法被标算完全爆踩，但是一步步推导并实现出自己独特的做法的过程令我乐在其中，很有成就感。而且，这个做法也大大的加深了我对数据结构优化 DP 的理解。