[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);
}