【BZOJ2090/2089】[Poi2010]Monotonicity

给出N个正整数a[1..N]，再给出K个关系符号（>、<或=）s[1..k]。
选出一个长度为L的子序列（不要求连续），要求这个子序列的第i项和第i+1项的的大小关系为s[(i-1)mod K+1]。
求出L的最大值。

第一行两个正整数，分别表示N和K (N, K <= 500,000)。
第二行给出N个正整数，第i个正整数表示a[i] (a[i] <= 10^6)。
第三行给出K个空格隔开关系符号（>、<或=），第i个表示s[i]。

一个正整数，表示L的最大值。

#include <cstdio>#include <iostream>#include <cstring>#define lson x<<1#define rson x<<1|1using namespace std;int t[500010],v[500010],f[500010];char str[5];int n,m,nm,ans;struct SAG{	int sm[4000010];	void pushup(int x)	{		sm[x]=max(sm[lson],sm[rson]);	}	void updata(int l,int r,int x,int p,int v)	{		if(l==r)		{			sm[x]=v;			return ;		}		int mid=l+r>>1;		if(p<=mid)	updata(l,mid,lson,p,v);		else	updata(mid+1,r,rson,p,v);		pushup(x);	}	int query(int l,int r,int x,int a,int b)	{		if(a>b)	return 0;		if(a<=l&&r<=b)	return sm[x];		int mid=l+r>>1;		if(b<=mid)	return query(l,mid,lson,a,b);		if(a>mid)	return query(mid+1,r,rson,a,b);		return max(query(l,mid,lson,a,b),query(mid+1,r,rson,a,b));	}}s[2];int s2[1000010];int max(int a,int b,int c){	return max(max(a,b),c);}int main(){	scanf("%d%d",&n,&m);	int i,j;	for(i=1;i<=n;i++)	scanf("%d",&v[i]),nm=max(v[i],nm);	for(i=1;i<=m;i++)	{		scanf("%s",str);		if(str[0]==‘>‘)	t[i]=0;		if(str[0]==‘<‘)	t[i]=1;		if(str[0]==‘=‘)	t[i]=2;	}	for(i=1;i<=n;i++)	{		f[i]=max(s[0].query(1,nm,1,v[i]+1,nm),s[1].query(1,nm,1,1,v[i]-1),s2[v[i]])+1;		ans=max(ans,f[i]);		j=t[(f[i]-1)%m+1];		if(j==2)	s2[v[i]]=max(f[i],s2[v[i]]);		else	s[j].updata(1,nm,1,v[i],f[i]);	}	printf("%d",ans);	return 0;}