Solution
这显然是求 \(\mathsf{LIS}\) 的模板多了一维限制，转移方程为 \(f_i=\max\limits_{j<i,a_i\ge mx_j,mn_i\ge a_j}f_j+1\)，其中 \(f_i\) 表示以 \(i\) 结尾的最长子序列，\(mx_i,mn_i\) 表示 \(a_i\) 能变化到的最大值和最小值，因为介于 \(mx_i\) 和 \(mn_i\) 之间的数都没有用。
对于方程的这三个限制，可以当三维偏序来做，每次用 \(f_i\) 更新 \((a_i,mx_i)\) 矩形内的最大值，查询时查 \((mn_i,a_i)\) 内的最大值即可。
实现的话，可以用 \(\mathsf{CDQ}\) 分治或树套树，这里我用了二维树状数组，用 pb_ds 的哈希表 gp_hash_table 来实现类似的动态开点。
Code
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
const int N=1e5+5;
int n,m,mv,ans,a[N],mn[N],mx[N];
gp_hash_table<int,int>c[N];
inline void add(int x,int y,int v){
for(int i=x;i<=mv;i+=i&-i)
for(int j=y;j<=mv;j+=j&-j)
c[i][j]=max(c[i][j],v);
}
inline int ask(int x,int y){
int res=0;
for(int i=x;i;i-=i&-i)
for(int j=y;j;j-=j&-j)
res=max(res,c[i][j]);
return res;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",a+i),mv=max(mv,mx[i]=mn[i]=a[i]);
for(int i=1,x,y;i<=m;i++){
scanf("%d%d",&x,&y);
mx[x]=max(mx[x],y);
mn[x]=min(mn[x],y);
mv=max(mv,mx[x]);
}
for(int i=1;i<=n;i++){
int res=ask(mn[i],a[i])+1;
add(a[i],mx[i],res);
ans=max(ans,res);
}printf("%d\n",ans);
return 0;
}