第一种有10分 第二种a了

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int c[N],dp[N];
struct node
{
    int x,id,maxx,minn;
};
node a[N];
bool cmp1(node cjr,node jxx)
{
    return cjr.maxx<jxx.maxx;
}
bool cmp2(node jxx,node cjr)
{
    return jxx.x<cjr.x;
}
int lowbits(int x)
{
    return x&(-x);
}
void add(int i,int k)
{
    while(i<=n)
    {
        c[i]=max(c[i],k);
        i+=lowbits(i);
    }
}
int query(int i)
{
    int sum=-1;
    while(i>0)
    {
        sum=max(sum,c[i]);
        i-=lowbits(i);
    }
    return sum;
}
void clean(int i)
{
    while(i<=n)
    {
        c[i]=0;
        i+=lowbits(i);
    }
    return;
}
void cdq(int l,int r)
{
    if(l==r)
    {
        dp[l]=max(dp[l],1);
        return;
    }
    int mid=l+r>>1;
    cdq(l,mid);
    sort(a+l,a+1+mid,cmp1);
    sort(a+mid+1,a+r+1,cmp2);
    for(int i=mid+1,j=l;i<=r;i++)
    {
        while(a[i].x>=a[j].maxx&&j<=mid)
        {
            add(a[j].x,dp[a[j].id]);
            j++;
        }
        dp[a[i].id]=max(dp[a[i].id],query(a[i].minn)+1);
    }
    for(int i=l;i<=mid;i++)
        clean(a[i].x);
    cdq(mid+1,r);
    return;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].x);
        a[i].maxx=a[i].minn=a[i].x;
        a[i].id=i;
    }
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        a[x].maxx=max(a[x].maxx,y);
        a[x].minn=min(a[x].minn,y);
    }
    cdq(1,n);
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,dp[i]);
    printf("%d",ans);
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int c[N],dp[N],val[N],maxx[N],minn[N],p[N];
bool cmp1(int i,int j)
{
    return maxx[i]<maxx[j];
}
bool cmp2(int i,int j)
{
    return val[i]<val[j];
}
int lowbits(int x)
{
    return x&(-x);
}
void add(int i,int k)
{
    while(i<=n)
    {
        c[i]=max(c[i],k);
        i+=lowbits(i);
    }
}
int query(int i)
{
    int sum=-1;
    while(i>0)
    {
        sum=max(sum,c[i]);
        i-=lowbits(i);
    }
    return sum;
}
void clean(int i)
{
    while(i<=n)
    {
        c[i]=0;
        i+=lowbits(i);
    }
    return;
}
void cdq(int l,int r)
{
    if(l==r)
    {
        dp[l]=max(dp[l],1);
        return;
    }
    int mid=l+r>>1;
    cdq(l,mid);
    for(int i=l;i<=r;i++)
        p[i]=i;
    sort(p+l,p+1+mid,cmp1);
    sort(p+mid+1,p+r+1,cmp2);
    for(int i=mid+1,j=l;i<=r;i++)
    {
        while(val[p[i]]>=maxx[p[j]]&&j<=mid)
        {
            add(val[p[j]],dp[p[j]]);
            j++;
        }
        dp[p[i]]=max(dp[p[i]],query(minn[p[i]])+1);
    }
    for(int i=l;i<=mid;i++)
        clean(val[i]);
    cdq(mid+1,r);
    return;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&val[i]);
        maxx[i]=minn[i]=val[i];
    }
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        maxx[x]=max(maxx[x],y);
        minn[x]=min(minn[x],y);
    }
    cdq(1,n);
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,dp[i]);
    printf("%d",ans);
}