YbtOJ NOIP2020 模拟赛 B 组 Day3 C.波动序列【dp】【线段树】

题目：

传送门

题意：

给出$3$个长度为$n$的序列，我们在这些序列的每一列选择一个或不选数，满足如下的条件$：$
问这样我们能构造出的序列最长是多少

分析：

设$f_{i,j,k}(k=0/1/2)$表示当前选到第$i$位，选出的最后一个数的大小为$j$，$k=0$表示上一个数是$1or2$序列的数，$k=1$表示的当前的单调性是递增的，$k=2$表示的当前的单调性是递减的
当$k=0$的时候，我们只需保证和上个数的大小关系就可以转移过来
当$k=1/2$的时候，我们看到序列的限制条件里的单调性是从$s_{l?1}$开始的，所以第$l?1$的位置一定不是来自序列$3$的，故$k=1$不能从$k=2$转移来，$k=2$不能从$k=1$转移来
我们发现我们转移的时候可以通过线段树来找到上一个位置在哪里，进而转移

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<queue>
#define LL long long
using namespace std;
inline LL read()
{
    LL s=0,f=1; char c=getchar();while(c<'0'||c>'9') {
    if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9') {
    s=s*10+c-'0';c=getchar();}return s*f;
}
struct tree{
    int w[400005];void change(int k,int L,int R,int pos,int val){
    if(L==R) {
    w[k]=max(w[k],val);return;}int mid=(L+R)>>1;if(pos<=mid) change(k*2,L,mid,pos,val);else change(k*2+1,mid+1,R,pos,val);w[k]=max(w[k*2],w[k*2+1]);} int ask(int k,int L,int R,int l,int r){
    if(L==l&&R==r) return w[k];int mid=(L+R)>>1;if(r<=mid) return ask(k*2,L,mid,l,r);if(l>mid) return ask(k*2+1,mid+1,R,l,r);return max(ask(k*2,L,mid,l,mid),ask(k*2+1,mid+1,R,mid+1,r));}
}t,tup,tdown;
int a[100005],b[100005],c[100005],ls[300005];
int main()
{
    freopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout);int n=read(),len=0;for(int i=1;i<=n;i++) ls[++len]=a[i]=read();for(int i=1;i<=n;i++) ls[++len]=b[i]=read();for(int i=1;i<=n;i++) ls[++len]=c[i]=read();sort(ls+1,ls+1+len);len=unique(ls+1,ls+1+len)-ls-1; for(int i=1;i<=n;i++){
    a[i]=lower_bound(ls+1,ls+1+len,a[i])-ls;b[i]=lower_bound(ls+1,ls+1+len,b[i])-ls;c[i]=lower_bound(ls+1,ls+1+len,c[i])-ls;}for(int i=1;i<=n;i++){
    int fa=max(t.ask(1,1,len,1,a[i]),max(tdown.ask(1,1,len,1,a[i]),tup.ask(1,1,len,1,a[i])))+1;int fb=max(t.ask(1,1,len,b[i],len),max(tdown.ask(1,1,len,b[i],len),tup.ask(1,1,len,b[i],len)))+1;int fcup=max(t.ask(1,1,len,1,c[i]),tup.ask(1,1,len,1,c[i]))+1;int fcdown=max(t.ask(1,1,len,c[i],len),tdown.ask(1,1,len,c[i],len))+1;t.change(1,1,len,a[i],fa); t.change(1,1,len,b[i],fb);tup.change(1,1,len,c[i],fcup);tdown.change(1,1,len,c[i],fcdown);}cout<<max(t.w[1],max(tup.w[1],tdown.w[1]));return 0;
}