[USACO22OPEN] Up Down Subsequence P
注意到这个问题是不弱于直接求 LIS 的，因此考虑 dp。
设 \(f_i\) 表示以 \(i\) 结尾的最长这个什么串的长度，显然没办法直接转移，那么暴力的想法就是多设一维，这样自然就寄了。我们考虑到这样一件事情：如果我们假装对于所有的 \(j\)，\(j < f_i\) 时以 \(i\) 结尾的长度为 \(j\) 的子序列都可行，这样就可以直接维护两个 BIT 转移了，但是正确性可能会有问题。
我们其实只需要求出正确的 \(f_i\)，假设下一个转移的本来应该是 U，那么我们找到在 \(f_i\) 之前的第一个 \(D\)，然后认为从 \(i\) 也可以转移出这个 D。那么能转移 D 出去的点按照是否比原先转移 D 的那个点小分为两部分，对于原先不能转移的部分，我们注意到其实可以从中间的点转移出更大的答案，因此对转移没有影响；而对于原先就可以转移的部分则显然是正确的。因此这个做法是对的！
const int N = 3e5 + 10;
int n, a[N];
char s[N];
struct BIT {
int lowbit(int x) {
return x & -x;
}
int tr[N];
void add(int x, int y) {
for(; x <= n; x += lowbit(x))
tr[x] = max(tr[x], y);
}
int query(int x) {
int res = 0;
for(; x; x -= lowbit(x))
res = max(res, tr[x]);
return res;
}
}s1, s2;
int f[N];
int pre[N][2];
int main() {
read(n);
for(int i = 1; i <= n; ++i)
read(a[i]);
scanf("%s",s + 1);
for(int i = 1; i < n; ++i) {
pre[i][0] = pre[i - 1][0], pre[i][1] = pre[i - 1][1];
if(s[i] == 'U') pre[i][0] = i;
else pre[i][1] = i;
}
int ans = 0;
for(int i = 1; i <= n; ++i) {
f[i] = max(s1.query(a[i]), s2.query(n - a[i] + 1)) + 1;
ans = max(ans, f[i]);
if(i < n) {
s1.add(a[i], pre[f[i]][0]);
s2.add(n - a[i] + 1, pre[f[i]][1]);
}
}
printf("%d\n",ans - 1);
}