设f[i]是以i位置为结尾的最长满足条件子序列的长度

那么j能转移到i的条件是，$j<i , max[j]<=a[i] , a[j]<=min[i]$，其中max和min表示这个位置能变化出来的最大值或最小值

这个东西用一个cdq来做

具体来说，先做左半区间，然后左边按max排序，右边按a排序，把左边的f按a为下标加到树状数组里，右面的用min来查，最后在做右半区间

1 #include
     
       2 #define CLR(a,x) memset(a,x,sizeof(a)) 3 using namespace std; 4 typedef long long ll; 5 typedef unsigned long long ull; 6 typedef pair
      
        pa; 7 const int maxn=1e5+10; 8  9 inline ll rd(){10     ll x=0;char c=getchar();int neg=1;11     while(c<'0'||c>'9'){
   if(c=='-') neg=-1;c=getchar();}12     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();13     return x*neg;14 }15 16 int N,M,V=1e5,a[maxn],ma[maxn],mi[maxn],f[maxn],ord[maxn];17 18 inline bool cmp1(int x,int y){
   return a[x]
       
        =r) return;32     int m=l+r>>1;33     cdq(l,m);34     for(int i=l;i<=r;i++) ord[i]=i;35     sort(ord+l,ord+m+1,cmp1),sort(ord+m+1,ord+r+1,cmp2);36     int p=l,q=m+1;37     for(;q<=r;q++){38         for(;p<=m&&a[ord[p]]<=mi[ord[q]];p++) change(ma[ord[p]],f[ord[p]]);39         f[ord[q]]=max(f[ord[q]],query(a[ord[q]])+1);40     }41     for(p=l;p<=m;p++) change(ma[ord[p]],0);42     cdq(m+1,r);43 }44 45 int main(){46     //freopen("","r",stdin);47     int i,j,k;48     N=rd(),M=rd();49     for(i=1;i<=N;i++)50         a[i]=ma[i]=mi[i]=rd(),f[i]=1;51     for(i=1;i<=M;i++){52         int x=rd(),y=rd();53         ma[x]=max(ma[x],y),mi[x]=min(mi[x],y);54     }55     cdq(1,N);56     int ans=0;57     for(i=1;i<=N;i++) ans=max(ans,f[i]);58     printf("%d\n",ans);59     return 0;60 }