一个序列在所有变换中都单调不降的条件是i<j,a[i]<=min[j],mx[i]<=a[j],所以套CDQ就行了。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 100005
#define inf 0x3f3f3f3f
using namespace std;
int n,m;
int a[N];
int f[N];
int mx[N],mn[N];
int tmp[N];
int v[N];
int res;
bool cmp(int x,int y)
{
if(x<=res&&y<=res)return mx[x]<mx[y];
if(x<=res)return mx[x]<=a[y];
if(y<=res)return a[x]<mx[y];
return a[x]<a[y];
}
int dp[N];
struct node
{
int lazy,zhi;
}aa[N*];
void push_down(int x)
{
if(aa[x].lazy!=)
{
aa[x*].zhi=aa[x*+].zhi=-inf;
aa[x*].lazy=aa[x*+].lazy=;
aa[x].lazy=;
}
return ;
}
int qur(int x,int l,int r,int ll,int rr)
{
if(l>=ll&&r<=rr)
{
return aa[x].zhi;
}
push_down(x);
int mid=(l+r)>>;
if(rr<=mid)return qur(x*,l,mid,ll,rr);
if(ll>mid)return qur(x*+,mid+,r,ll,rr);
return max(qur(x*,l,mid,ll,rr),qur(x*+,mid+,r,ll,rr));
}
void gai(int x,int l,int r,int pos,int z)
{
if(l==r)
{
aa[x].zhi=max(aa[x].zhi,z);return ;
}
push_down(x);
int mid=(l+r)>>;
if(pos<=mid)gai(x*,l,mid,pos,z);
else gai(x*+,mid+,r,pos,z);
aa[x].zhi=max(aa[x*].zhi,aa[x*+].zhi);
}
void solve(int l,int r)
{
if (l==r)
{
f[l]=max(f[l],);
return ;
}
int mid=(l+r)>>;
solve(l,mid);res=mid;
int cnt=;
for(int i=l;i<=r;i++)tmp[++cnt]=i;
sort(tmp+,tmp+cnt+,cmp);
aa[].lazy=;aa[].zhi=-inf;
for(int i=;i<=cnt;i++)
{
if(tmp[i]<=mid)gai(,,,a[tmp[i]],f[tmp[i]]);
else f[tmp[i]]=max(f[tmp[i]],qur(,,,,mn[tmp[i]])+);
}
solve(mid+,r);
}
int main()
{
scanf("%d%d",&n,&m);
memset(mx,0xcf,sizeof(mx));
memset(mn,0x3f,sizeof(mn));
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
mx[i]=mn[i]=a[i];
}
for(int i=;i<=m;i++)
{
int t1,t2;
scanf("%d%d",&t1,&t2);
mx[t1]=max(mx[t1],t2);
mn[t1]=min(mn[t1],t2);
}
solve(,n);
int ans=;
for(int i=;i<=n;i++)ans=max(ans,f[i]);
printf("%d\n",ans);
return ;
}