【BZOJ2090/2089】[Poi2010]Monotonicity
Description
给出N个正整数a[1..N]，再给出K个关系符号（>、<或=）s[1..k]。
选出一个长度为L的子序列（不要求连续），要求这个子序列的第i项和第i+1项的的大小关系为s[(i-1)mod K+1]。
求出L的最大值。
Input
第一行两个正整数，分别表示N和K (N, K <= 500,000)。
第二行给出N个正整数，第i个正整数表示a[i] (a[i] <= 10^6)。
第三行给出K个空格隔开关系符号（>、<或=），第i个表示s[i]。
Output
一个正整数，表示L的最大值。
Sample Input
7 3
2 4 3 1 3 5 3
< > =
2 4 3 1 3 5 3
< > =
Sample Output
6
题解：一开始没看到不要求连续，以为是一道KMP的裸题。。。
我们令f[i]表示第i个数最多能成为子序列的第f[i]项，所以当我们确定f[i]后，i的下一项和i的关系是确定的，所以我们考虑如何实现查询
我们根据三种关系，维护2个权值线段树和一个数组，分别对应>,<,=。=我就不说了，我们以<举例
如果f[i]对应的符号是<，那么我们将它放到<所对应的权值线段树中，权值线段树上v[i]位置的值就是f[i]，然后在枚举到j的时候，就查询[1,v[j]-1]上f[]的最大值，再+1就能更新f[j]
#include <cstdio>
#include <iostream>
#include <cstring>
#define lson x<<1
#define rson x<<1|1
using 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;
}