树状数组优化dp
可以证明最优解一定是通过之前的最优转移过来的，所以每一个点只需要保存以该节点为结尾的最长长度即可
对于不同符号，等于号维护数组，大于小于维护树状数组
#include#include #include #include #include #define N 500005using 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;}