题目链接
题意分析
我们假设每一个数都有一个变动范围\([L_i,R_i]\)
那么我们令\(dp[i]\)表示以\(i\)结尾的最长不下降子序列的长度
那么就是\(dp[i]=max\{dp[j]+1\}\)
转移的条件是
\(1.j<i\)
\(2.r_j≤a_i\)
\(3.a_j≤l_i\)
所以这就是一个三位偏序问题了
同时需要注意的是
我们当前对于\([l,r]\)区间
我们由于必须要遵循从左向右更新的性质
所以先处理好\([l,mid]\)有\([l,mid]\)向\((mid,r]\)转移
然后再处理\((mid,r]\)
至于具体的处理
我们对于\([l,mid]\)需要按照\(r_i\)从小到大排序
对于\((mid,r]\)需要按照\(a_i\)从小到大排序
然后最后一维使用树状数组处理即可
CODE:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<list>
#include<set>
#include<deque>
#include<vector>
#include<ctime>
#define ll long long
#define inf 0x7fffffff
#define N 500008
#define IL inline
#define M 100011
#define D double
#define maxn 100002
#define R register
using namespace std;
template<typename T>IL void read(T &_)
{
T __=0,___=1;char ____=getchar();
while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();}
while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();}
_=___ ? __:-__;
}
/*-------------OI使我快乐-------------*/
int n,m,ans;
int tre[M],dp[M];
struct Node{
int id,lx,rx,num;
}e[M];
IL bool cmp1(const Node &A,const Node &B)
{return A.rx<B.rx;}
IL bool cmp2(const Node &A,const Node &B)
{return A.num<B.num;}
IL bool cmp3(const Node &A,const Node &B)
{return A.id<B.id;}
IL void add(int x,int y)
{for(;x<=maxn;x+=x&-x) tre[x]=max(tre[x],y);}
IL int qury(int x)
{int res=0;for(;x;x-=x&-x) res=max(res,tre[x]);return res;}
IL void clean(int x)
{for(;x<=maxn;x+=x&-x) tre[x]=0;}
IL void solve(int le,int ri)
{
if(le==ri) return;
int mid=(le+ri)>>1;
solve(le,mid);
sort(e+le,e+mid+1,cmp1);sort(e+mid+1,e+ri+1,cmp2);
int cdy=le,wzy=mid+1;
for(;wzy<=ri;++wzy)
{
for(;cdy<=mid&&e[cdy].rx<=e[wzy].num;++cdy)
add(e[cdy].num,dp[e[cdy].id]);
dp[e[wzy].id]=max(dp[e[wzy].id],qury(e[wzy].lx)+1);
}
for(R int i=le;i<cdy;++i) clean(e[i].num);
sort(e+mid+1,e+ri+1,cmp3);
solve(mid+1,ri);
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n);read(m);
for(R int i=1;i<=n;++i)
{
read(e[i].num);e[i].id=i;;
e[i].lx=e[i].rx=e[i].num;
}
for(R int i=1,x,y;i<=m;++i)
{
read(x);read(y);
e[x].lx=min(e[x].lx,y);
e[x].rx=max(e[x].rx,y);
}
// for(R int i=1;i<=n;++i)
// printf("%d %d %d %d\n",e[i].num,e[i].lx,e[i].rx,e[i].id);
for(R int i=1;i<=n;++i) dp[i]=1;
solve(1,n);
for(R int i=1;i<=n;++i) ans=max(ans,dp[i]);
printf("%d\n",ans);
// fclose(stdin);
// fclose(stdout);
return 0;
}