自动搬运

查看原文

来自洛谷，原作者为

	xiaoyaowudi 想回到最初原点 拨琴弦唱起岁月 不畏惧未来渺远 只牵挂那心愿

搬运于2025-08-24 22:37:35，当前版本为作者最后更新于2022-04-05 09:40:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意

给定一个排列 $p$ 和一个字符串 $s$，$s$ 由大于小于号组成，求 $p$ 中最长的子序列 $t_0,t_1,t_2\cdots t_k$ 使得 $t_i,t_{i+1}$ 的大小关系和 $s_{i+1}$ 相同。

$n\le 3\times 10^5$。

分析

下文假设如果 $x$ 表示一个大于小于号，那么 $\hat{x}$ 表示相反的符号。

设 $f_i$ 为 $p_1,p_2,\cdots p_i$ 中以 $p_i$ 结尾的子序列在 $s_i$ 中能匹配的最长前缀长度。

下证，存在一个下标子序列 $x_0,x_1\cdots x_{f_i},x_{f_i}=i$ 使得 $\forall 0\le k\le f_i,k=f_{x_k}$，$p_{x_0},\cdots p_{x_{f_i}}$ 能够匹配 $s_1,s_2\cdots s_{f_i}$。

假设 $t_0,t_1,\cdots t_{f_i}$ 为 $x_{f_k},x_{f_k-1},\cdots x_0$ 字典序最小时对应的 $p_{x_0},p_{x_1}\cdots p_{x_{f_i}}$，因为 子序列个数有限，因此 $t$ 存在。

若存在 $0\le k \lt f_i$ 使得 $f_{x_k}\gt f_i$，

假设 $j=x_k,r=f_j,l=f_i$，$j$ 达成最大匹配时子序列为 $b_0,b_1\cdots b_r$。

那么 $b_{k}\; s_{k+1}\;b_{k+1}\;s_{k+2}\cdots b_{r-1}\;s_{r}\;b_{r}$，且 $b_r=t_k \;s_{k+1}\; t_{k+1}\;s_{k+2}\;\cdots s_{l}\;t_{l} $。

下证 $b_{k},b_{k+1},\cdots b_{r}=t_k,\cdots t_l$ 存在一个长度为 $l-k+1$ 或 $l-k$ 的子序列能够匹配 $s_{k+1},s_{k+2}\cdots s_{l+1}$ 或 $s_{k+1},s_{k+2}\cdots s_l$。

若 $\forall k\le m\lt l$，$b_{k} \;s_{k+1}\;t_{k+1}$ 不成立。

那么分两种情况，$s_{k+1}=s_{k+2}=\cdots s_{l}$。

那么 $b_{l}\; \hat{s_l}\;b_{l-1}\; \hat{s_{l}}\;t_{l}$，即 $b_{l} \;\hat{s_l}\; t_l$，于是 $s_{l+1},s_{l+2}\cdots s_{r}$ 中必存在一个前缀使得 $s_{l+1},s_{l+2},\cdots s_{d},l\lt d\le r$，且 $s_{k+1}=s_{k+2}=\cdots =s_{l}=s_{l+1}\cdots s_{d-1}=\hat{s_d}$，由传递性可知 $t_l\;s_{l}\;b_{l}\;s_{l+1}\; b_{l+1} \cdots s_{d-1}\;b_{d-1}$ 可以推出 $b_{d-1} \;\hat{s_{d-1}}\;t_{l}$ ，又 $\hat{s_{d-1}}=s_d$ 那么 $b_{d-1}\; s_d\; t_{l}$，于是存在一个以 $i$ 结尾的子序列可以匹配 $s$ 的前缀长度为 $d\gt l=f_i$ 矛盾！

否则存在相邻两项 $s_{d+1}=\hat{s_{d}},k\lt d\lt l$，那么 $b_{d-1}\;\hat{s_d}\; t_d$，$b_{d}\;\hat{s_d} \;b_{d-1}$，$t_{d+1}\;s_{d+1}\;b_{d}$，$t_{d}\;s_{d+1}\;t_{d+1}$，于是 $b_{d-1}\;\hat{s_{d}}\;t_{d}\;s_{d+1}\;t_{d+1}\;s_{d+1}\;b_{d}\;\hat{s_{d}}\;b_{d-1}$。

由 $s_{d+1}=\hat{s_d}$ 可知中间四个符号都相同，那么 $b_{d-1}\;s_{d-1}\; b_{d-1}$ 矛盾！

所以 $\exists k\le m\lt l$，使得 $b_{k}\;s_{k+1}\;t_{k+1}$。

那么此时把 $t_{m+1},t_{m+2}\cdots t_{l}$ 接到 $b_{0},b_{1}\cdots b_{m}$ 后面也是一组合法的解，此时 $x^{\prime}_{f_i},x^{\prime}_{f_i-1},\cdots x^{\prime}_0$ 的字典序更小，因为 $x_{m}$ 变小了而 $x_{m+1},\cdots x_{f_i}$ 均没变化。

与假设矛盾！

若存在 $0\le k\lt f_{i}$ 使得 $f_{x_k}\neq k$ ，那么这时令 $j=x_k,r=f_{j},l=r$，$j$ 达成最大匹配时子序列为 $b_0,b_1\cdots b_r$。

与上面同理，只有 $s_{k+1}=s_{k+2}\cdots =s_l$ 时会推出 $b_{r}=b_{l}\;\hat{s_{l}}\;t_{l}$，而 $b_r=t_k$ ，由 $s_{k+1}=s_{k+2}\cdots =s_l$ 得出 $b_r\; s_l\;t_l$，矛盾！

命题成立。

因此我们可以直接用树状数组维护 dp 值。

Code

#include <cstdio>
#include <algorithm>
using namespace std;
constexpr int N=300010;
int b1[N],b2[N];
void upd(int *b,int x,int v){for(;x<N;x+=(x&(-x))) b[x]=max(b[x],v);}
int qry(int *b,int x){int ans=0;for(;x;x-=(x&(-x))) ans=max(ans,b[x]);return ans;}
char s[N];int n,a[N];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);scanf("%s",s+1);int ans=0;
	for(int i=1;i<=n;++i){
		int f=max(qry(b1,a[i]-1),qry(b2,n-a[i]));ans=max(ans,f);
		if(s[f+1]=='U') upd(b1,a[i],f+1);else upd(b2,n-a[i]+1,f+1);
	}
	printf("%d\n",ans);
	return 0;
}