题意

给定长度为 的序列 ，求最长子序列使得其按 中顺序相邻两数的大小关系是给定字符串 的前缀。

思路

考虑有 简单 DP，设 表示 前缀能与 前缀匹配。

发现我们存的是 ，也就意为这这个 DP 的信息密度非常的低，考虑提高一下信息密度。

大胆猜想我们只用留 中最大的一个 就可以了，写一发就过了，很快啊，考虑证明。

---

不妨设现在有 与 的两条转移链，我们令 只是前面的转移情况不同使得 ，那么可以证明 一定可以等于 或者 一定可以等于 （然后把相等的那个作为 与 向后归纳）。

我们称前一个转移链中的大小关系为 ，后一个为

我们令 ，若我们要证明的东西存在，则可以调整出这个状况，于是我们有 。

---

先考虑边界情况，显然，若 或者 不存在，则命题成立。

然后发现若 则有 ，由于 于是 的集合与 的集合是一样的。

那么 ，比如说 ，而因为上面提到过的 ，所以有 ，那我们就知道，，所以任意一个 都是合法的 ，答案仍然更劣。

CODE

具体维护由于只增 只增不减，故可以使用树状数组。

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1000010,FSIZE=1<<26;
int n,a[N],ans;
void cmax(int &x,int y){if(y>x) x=y;}
struct FT{
    int a[N];
    int query(int x){
        int re=0;
        for(;x;x-=x&-x) cmax(re,a[x]);
        return(re);
    }
    void modify(int x,int p){for(;x<=n;x+=x&-x) cmax(a[x],p);}
}up,dw;
char BuF[FSIZE],*s=BuF;
template<typename T>void read(T &x){
    for(;48>*s||*s>57;++s);
    for(x=0;47<*s&&*s<58;x=x*10+(*s++^48));
}
int main(){
    fread(BuF,1,FSIZE,stdin);
    read(n);
    for(int i=0;i<n;++i) read(a[i]);
    for(;*s<32;++s);
    for(int i=0;i<n;++i){
        int x=max(up.query(a[i]),dw.query(n-a[i]+1));
        cmax(ans,x);
        if(s[x++]=='U') up.modify(a[i],x);
        else dw.modify(n-a[i]+1,x);
    }
    printf("%d\n",ans);
    return(0);
}s