[Poi2010]Monotonicity 2
题目
给出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 32 4 3 1 3 5 3< > =OUTPUT
6
解题报告
考试时连最最最简单的DP都没想出来，就打了个DFS- -
正解：
我们先考虑只有一种符号的情况，比如说考虑<，那么不就变成了求最长上升子序列吗。
同样的，我们扩展至三种符号：
for(int i=;i<=n;i++){
f[i]=;
for(int j=;j<=i-;j++){
int tmp(f[j]%k+);
if(op[tmp]=='='&&a[j]==a[i]&&f[j]+>f[i])
f[i]=f[j]+;
if(op[tmp]=='>'&&a[j]>a[i]&&f[j]+>f[i])
f[i]=f[j]+;
if(op[tmp]=='<'&&a[j]<a[i]&&f[j]+>f[i])
f[i]=f[j]+;
}
}
这就是最最最简单的DP，然而我们知道，这玩意是O(n²)的复杂度，显然会T，那么我们就需要优化一下了。
我们发现，转移时有O(n)的复杂度来找最大值，那么我们想，是否可以把这个过程优化呢？自然可以，我们的目的在于找到权值符合条件的最大f值，所以，我们需要一个新的东西来完成它：
权值线段树
这是一个神奇的数据结构- -，好吧，也不怎么神奇，它在这道题里是以权值为下标，存入该点最优解的一种线段树，它就可以完成这个伟大的任务啦。
我们需要3棵树（其实2棵也可以，相等的那个用数组模拟即可实现，只是我比较懒- -），每一棵树存以该符号为后面所接符号的权值的最优解（好绕啊- -），这样我们在找的时候，取出每棵树中符合权值条件的最优解，三解进行比较，选出最优以确定符号，继续转移并更新相应的线段树即可。
（我语文表达能力好弱啊）
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
inline int read(){
int sum();
char ch(getchar());
for(;ch<''||ch>'';ch=getchar());
for(;ch>=''&&ch<='';sum=sum*+(ch^),ch=getchar());
return sum;
}
inline char init(){
char ch(getchar());
for(;ch!='='&&ch!='>'&&ch!='<';ch=getchar());
return ch;
}
inline int my_max(int a,int b){
return a>b?a:b;
}
int n,k;
int a[],op[];
int tr_d[],tr_x[],tr_e[];
int ad_d[],ad_x[],ad_e[];
inline void pushup_d(int i){
tr_d[i]=my_max(tr_d[i<<],tr_d[i<<|]);
}
inline void pushup_x(int i){
tr_x[i]=my_max(tr_x[i<<],tr_x[i<<|]);
}
inline void pushup_e(int i){
tr_e[i]=my_max(tr_e[i<<],tr_e[i<<|]);
}
inline void pushdown_d(int i){
if(ad_d[i]){
ad_d[i<<]=ad_d[i];
ad_d[i<<|]=ad_d[i];
tr_d[i<<]=ad_d[i];
tr_d[i<<|]=ad_d[i];
tr_d[i]=ad_d[i];
ad_d[i]=;
}
}
inline void pushdown_x(int i){
if(ad_x[i]){
ad_x[i<<]=ad_x[i];
ad_x[i<<|]=ad_x[i];
tr_x[i<<]=ad_x[i];
tr_x[i<<|]=ad_x[i];
tr_x[i]=ad_x[i];
ad_x[i]=;
}
}
inline void pushdown_e(int i){
if(ad_e[i]){
ad_e[i<<]=ad_e[i];
ad_e[i<<|]=ad_e[i];
tr_e[i<<]=ad_e[i];
tr_e[i<<|]=ad_e[i];
tr_e[i]=ad_e[i];
ad_e[i]=;
}
}
inline void update_d(int ll,int rr,int c,int l,int r,int i){
if(ll<=l&&r<=rr){
ad_d[i]=c;
tr_d[i]=c;
return;
}
pushdown_d(i);
int mid((l+r)>>);
if(ll<=mid)
update_d(ll,rr,c,l,mid,i<<);
if(rr>mid)
update_d(ll,rr,c,mid+,r,i<<|);
pushup_d(i);
}
inline void update_x(int ll,int rr,int c,int l,int r,int i){
if(ll<=l&&r<=rr){
ad_x[i]=c;
tr_x[i]=c;
return;
}
pushdown_x(i);
int mid((l+r)>>);
if(ll<=mid)
update_x(ll,rr,c,l,mid,i<<);
if(rr>mid)
update_x(ll,rr,c,mid+,r,i<<|);
pushup_x(i);
}
inline void update_e(int ll,int rr,int c,int l,int r,int i){
if(ll<=l&&r<=rr){
ad_e[i]=c;
tr_e[i]=c;
return;
}
pushdown_e(i);
int mid((l+r)>>);
if(ll<=mid)
update_e(ll,rr,c,l,mid,i<<);
if(rr>mid)
update_e(ll,rr,c,mid+,r,i<<|);
pushup_e(i);
}
inline int query_d(int ll,int rr,int l,int r,int i){
if(ll>rr)
return ;
if(ll<=l&&r<=rr)
return tr_d[i];
pushdown_d(i);
int mid((l+r)>>);
int ret();
if(ll<=mid)
ret=my_max(ret,query_d(ll,rr,l,mid,i<<));
if(rr>mid)
ret=my_max(ret,query_d(ll,rr,mid+,r,i<<|));
return ret;
}
inline int query_x(int ll,int rr,int l,int r,int i){
if(ll>rr)
return ;
if(ll<=l&&r<=rr)
return tr_x[i];
pushdown_x(i);
int mid((l+r)>>);
int ret();
if(ll<=mid)
ret=my_max(ret,query_x(ll,rr,l,mid,i<<));
if(rr>mid)
ret=my_max(ret,query_x(ll,rr,mid+,r,i<<|));
return ret;
}
inline int query_e(int ll,int rr,int l,int r,int i){
if(ll>rr)
return ;
if(ll<=l&&r<=rr)
return tr_e[i];
pushdown_e(i);
int mid((l+r)>>);
int ret();
if(ll<=mid)
ret=my_max(ret,query_e(ll,rr,l,mid,i<<));
if(rr>mid)
ret=my_max(ret,query_e(ll,rr,mid+,r,i<<|));
return ret;
}
int f[];
int mx();
int main(){
n=read(),k=read();
for(int i=;i<=n;i++)
a[i]=read(),mx=my_max(mx,a[i]);
for(int i=;i<=k;i++){
char ch(init());
if(ch=='>')
op[i]=;
if(ch=='<')
op[i]=;
if(ch=='=')
op[i]=;
}
f[]=;
if(op[]==)
update_d(a[],a[],f[],,mx,);
if(op[]==)
update_x(a[],a[],f[],,mx,);
if(op[]==)
update_e(a[],a[],f[],,mx,);
for(int i=;i<=n;i++){
int now(a[i]);
int ans_d(query_d(now+,mx,,mx,));
int ans_x(query_x(,now-,,mx,));
int ans_e(query_e(now,now,,mx,));
int ans(my_max(my_max(ans_d,ans_x),ans_e));
f[i]=ans+;
int o(op[ans%k+]);//cout<<i<<' '<<f[i]<<' '<<o<<endl;
if(o==)
update_d(now,now,f[i],,mx,);
if(o==)
update_x(now,now,f[i],,mx,);
if(o==)
update_e(now,now,f[i],,mx,);
}
int mxx();
for(int i=;i<=n;i++)
mxx=my_max(mxx,f[i]);
printf("%d",mxx);
}
写的极其丑- -，毕竟三颗线段树乱搞
凑合着看吧，其实理解了之后，一颗线段树，加不同的域，对传的参数进行处理，就可以达到三颗线段树的效果