bzoj 2089/2090: [Poi2010]Monotonicity 2 — 线段树优化dp
Contents
2090: [Poi2010]Monotonicity 2
Time Limit: 30 Sec Memory Limit: 259 MB
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
HINT
选出的子序列为2 4 3 3 5 3，相邻大小关系分别是< > = < >。
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;
}
发表评论