bzoj 2089/2090: [Poi2010]Monotonicity 2 — 线段树优化dp

2090: [Poi2010]Monotonicity 2

Time Limit: 30 Sec  Memory Limit: 259 MB

Description

Input

Output

Sample Input

Sample Output

HINT

Source

很好玩的方式

首先，我们考虑dp，用f[i]表示到第i位时的最长长度

所以这个时候他连接下一位的符号是固定的

这样我们就可以分三类：

如果是=，就开一个桶记录一下值为这个是的当前最优解

如果是<，我们可以推入一个下一位是小于号的线段树，以权值为下表，维护f值

然后下次更新f的时候，取出合法区间的最大的值就好了

如果是>，同理可以维护一个下一位是小于号的线段树

这样就可以做到时间复杂度O(nlogn)了

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 1000000007
#define ll long long
#define N 1000010
inline int rd()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,k,nn,a[N],op[N],f[N],ans;
struct segtr
{
	#define ls p<<1
	#define rs p<<1|1
	int mx[N<<2];
	void xg(int p,int l,int r,int x,int v)
	{
		if(l==r){mx[p]=v;return;}
		int mid=l+r>>1;
		x<=mid?xg(ls,l,mid,x,v):xg(rs,mid+1,r,x,v);
		mx[p]=max(mx[ls],mx[rs]);
	}
	int fd(int p,int l,int r,int L,int R)
	{
		if(L>R) return 0;
		if(l==L&&R==r) return mx[p];
		int mid=l+r>>1;
		if(R<=mid) return fd(ls,l,mid,L,R);
		if(L>mid) return fd(rs,mid+1,r,L,R);
		return max(fd(ls,l,mid,L,mid),fd(rs,mid+1,r,mid+1,R));
	}
}tr[2];
int ji[N];
int main()
{
	n=rd();k=rd();
	for(int i=1;i<=n;i++) a[i]=rd(),nn=max(a[i],nn);
	char ch[5];
	for(int i=1;i<=k;i++)
	{
		scanf("%s",ch);
		if(ch[0]=='>') op[i]=0;
		else if(ch[0]=='<') op[i]=1;
		else op[i]=2;
    }
	for(int i=1,tt;i<=n;i++)
	{
		tt=max(tr[0].fd(1,1,nn,a[i]+1,nn),tr[1].fd(1,1,nn,1,a[i]-1));
		f[i]=max(tt,ji[a[i]])+1;
		ans=max(ans,f[i]);
		tt=op[(f[i]-1)%k+1];
		if(tt==2) ji[a[i]]=max(f[i],ji[a[i]]);
		else tr[tt].xg(1,1,nn,a[i],f[i]);
	}
	printf("%d\n",ans);
	return 0;
}