树状数组优化dp

可以证明最优解一定是通过之前的最优转移过来的，所以每一个点只需要保存以该节点为结尾的最长长度即可

对于不同符号，等于号维护数组，大于小于维护树状数组

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<cmath>

#define N 500005

using namespace std;

int n,m,a[N],f[N],ans,c[2][2*N],ff[2*N],maxn;

char s[N];

int lowbit(int x){

    return x&(-x);

}

void update(int k,int x,int y){

    while(x<=maxn){

        c[k][x]=max(c[k][x],y);

        x+=lowbit(x);

    }

}

int query(int k,int x){

    int ans=0;

    while(x){

        ans=max(c[k][x],ans);

        x-=lowbit(x);

    }

    return ans;

}

int main()

{

    //freopen("mot.in","r",stdin);

    //freopen("mot.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++){

        scanf("%d",&a[i]);

        maxn=max(maxn,a[i]);

    }

    for(int i=1;i<=m;i++){

        s[i]=getchar();

        while(s[i]!='<'&&s[i]!='>'&&s[i]!='=')

        s[i]=getchar();

    }

    int x1,x2,x3; char ch;

    for(int i=1;i<=n;i++){

        x1=query(0,a[i]-1);

        x2=query(1,maxn-a[i]);

        x3=ff[a[i]];

        f[i]=max(x1,max(x2,x3))+1;

        ch=s[(f[i]-1)%m+1];

        if(ch=='<') update(0,a[i],f[i]);

        if(ch=='>') update(1,maxn-a[i]+1,f[i]);

        if(ch=='=') ff[a[i]]=max(ff[a[i]],f[i]);

    }

    for(int i=1;i<=n;i++){

        //printf("%d  %d\n",i,f[i]);

        ans=max(ans,f[i]);

    }

    printf("%d\n",ans);

    return 0;

}