题目链接：
题目大意在描述底下有。此处不赘述。
明显是个类似于LIS的dp。
令 $dp[i][j]$ 表示：
- $j=1$ 时表示已经处理了 $i$ 个数，上一个选的数来自序列 $A[0]$ 的最长长度
- $j=2$ 表示 $A[1]$
- $j=3$ 表示 $A[2]$ 且是单调递减
- $j=4$ 表示 $A[2]$ 且是单调递增
（为了方便，我们令 $seq[x]$ 表示当上文中的 $j=x$ 时表示哪个序列）
那么有转移方程：
- $dp[i][1]=\max\limits_{1\le j<i,k\in\{1,2,3,4\}}\{dp[j][k]:A[seq[k]][j]\le A[0][i]\}+1$（从前面任选一个更小的）
- $dp[i][2]=\max\limits_{1\le j<i,k\in\{1,2,3,4\}}\{dp[j][k]:A[seq[k]][j]\ge A[0][i]\}+1$（同理）
- $dp[i][3]=\max\limits_{1\le j<i,k\in\{1,2,3\}}\{dp[j][k]:A[seq[k]][j]\le A[0][i]\}+1$（因为第三个序列连续一段状态应相同，所以不能从4转移）
- $dp[i][4]=\max\limits_{1\le j<i,k\in\{1,2,4\}}\{dp[j][k]:A[seq[k]][j]\ge A[0][i]\}+1$（同上）
可以朴素dp，复杂度 $O(n^2)$。
优化？这个真的很像LIS，那么就用二分或者树状数组/线段树吧。
二分我不会……（当然二分可能做不了）
树状数组懒得打后缀最大了……
那就线段树吧，跟普通的LIS类似，开4棵线段树，分别维护 $j=1,2,3,4$。每次求一下前缀和后缀最大，然后插进线段树中即可。
（其实是可以只开3棵线段树的，$j=1,2$ 可以合在一起。但是我从前写的时候出锅了，以为是3棵线段树的锅，改成了4棵，后来发现不是这里出bug……懒得改了）
当然 $m\le 10^9$，需要离散化。
（注：离散化后最大的数可达 $3n$，所以要开4棵大小为 $3n$ 的线段树）
时间复杂度是 $O(n\log n)$。
代码+注释：（代码长得有点丑）
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
int n,a[maxn],b[maxn],c[maxn],tmp[maxn*],sz,ans=; //tmp是离散化用到的数组，sz是离散化后所有数的最大值，可以算是常数优化
int cnt,maxv[maxn*],ch[maxn*][]; //我用的动态开点线段树，一棵树节点数为约6n，而有4棵树
inline int lwrbnd(int x){ //离散化
return lower_bound(tmp+,tmp+sz+,x)-tmp;
}
struct segment{ //线段树维护区间最大
int n,root;
inline void pushup(int x){
maxv[x]=max(maxv[ch[x][]],maxv[ch[x][]]);
}
void build(int &x,int l,int r){
x=++cnt;
if(l==r) return;
int mid=l+r>>;
build(ch[x][],l,mid);
build(ch[x][],mid+,r);
}
segment(){}
segment(int n_):n(n_){build(root,,n);}
void update_(int x,int l,int r,int p,int k){
if(l==r) return void(maxv[x]=max(maxv[x],k)); //这里不能直接修改，如果之前相同位置的dp值更大则要保留
int mid=l+r>>;
if(mid>=p) update_(ch[x][],l,mid,p,k);
else update_(ch[x][],mid+,r,p,k);
pushup(x);
}
void update(int p,int k){
update_(root,,n,p,k);
}
int query_(int x,int L,int R,int l,int r){
if(L>=l && R<=r) return maxv[x];
int mid=L+R>>,ans=;
if(mid>=l) ans=max(ans,query_(ch[x][],L,mid,l,r));
if(mid<r) ans=max(ans,query_(ch[x][],mid+,R,l,r));
return ans;
}
int query(int l,int r){
return query_(root,,n,l,r);
}
}sgm1,sgm2,sgm3,sgm4; //4棵线段树
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",a+i),tmp[i]=a[i];
for(int i=;i<=n;i++) scanf("%d",b+i),tmp[i+n]=b[i];
for(int i=;i<=n;i++) scanf("%d",c+i),tmp[i+*n]=c[i];
sort(tmp+,tmp+*n+);
sz=unique(tmp+,tmp+*n+)-tmp-;
sgm1=segment(sz);sgm2=segment(sz);sgm3=segment(sz);sgm4=segment(sz); //建树（我的代码这里不能连等，否则4棵线段树实际的维护值一样）
for(int i=;i<=n;i++) a[i]=lwrbnd(a[i]),b[i]=lwrbnd(b[i]),c[i]=lwrbnd(c[i]); //离散化
for(int i=;i<=n;i++){
int tmp1=max(sgm1.query(,a[i]),max(sgm2.query(,a[i]),max(sgm3.query(,a[i]),sgm4.query(,a[i]))))+;
int tmp2=max(sgm1.query(b[i],sz),max(sgm2.query(b[i],sz),max(sgm3.query(b[i],sz),sgm4.query(b[i],sz))))+;
int tmp3=max(sgm1.query(,c[i]),max(sgm2.query(,c[i]),sgm3.query(,c[i])))+;
int tmp4=max(sgm1.query(c[i],sz),max(sgm2.query(c[i],sz),sgm4.query(c[i],sz)))+;
//上面四行是从线段树中查询前缀/后缀最大值并且更新
ans=max(ans,max(tmp1,max(tmp2,max(tmp3,tmp4))));
sgm1.update(a[i],tmp1);sgm2.update(b[i],tmp2);sgm3.update(c[i],tmp3);sgm4.update(c[i],tmp4); //插入线段树
}
printf("%d\n",ans);
}
线段树优化dp