#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
int n,k,n_,dp[100001],ads,xp,t;
struct value{
    int a,b,c,d;
}p[100001];
int lp[(1<<19)],_n;
inline void cin(int &x){
    x=0;
    bool f=false;
    char c='L';
    while((c<'0'||c>'9')&&c!='-')c=getchar();
    if(c=='-'){
        f=true;
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=x*10+c-'0';
        c=getchar();
    }
    if(f)x=-x;
}
inline void cout(int f){
    if(f<0){
    putchar('-');
    f=-f;
   }
   if(f>=10)cout(f/10);
   putchar(f%10+'0');
}
inline void add(int pl,int val){
    for(int i=pl;i<=n_;i+=(-i)&i){
        lp[i]=max(lp[i],val);
    }
}
inline void deleter(int pl){
    for(int i=pl;i<=n_;i+=(-i)&i){
        lp[i]=0;
    }
}
inline int query(int pl){
    int s=0;
    for(int i=pl;i>0;i&=i-1)s=max(s,lp[i]);
    return s;
}
inline bool cmpa(value x,value y){
    return x.a<y.a;
}
inline bool cmpb(value x,value y){
    if(x.b==y.b)return x.a<y.a;
    else return x.b<y.b;
}
inline bool cmpc(value x,value y){
    if(x.c==y.c)return x.a<y.a;
    else return x.c<y.c;
}
inline void solve(int l,int r){
    if(l==r){ads=max(ads,dp[p[l].a]);return;}
    int mid=(l+r)>>1;
    solve(l,mid);
    sort(p+l+1,p+mid+1,cmpb);
    sort(p+mid+2,p+r+1,cmpc);
    for(int i=l-1,j=mid+1;j<=r;j++){
        while(i<mid&&p[i+1].b<=p[j].c){i++,add(p[i].d,dp[p[i].a]+1);}
        dp[p[j].a]=max(dp[p[j].a],query(p[j].b));
    }
    for(int i=l;i<=mid&&p[i].b<=p[r].c;i++)deleter(p[i].d);
    sort(p+l+1,p+r+1,cmpa);
    solve(mid+1,r);
}
int main(){
    cin(n),cin(k);
    n_=1;
    while(n_<100000)n_*=2;
    for(int i=1;i<=n;i++){
        cin(p[i].b);
        p[i].a=i;
        p[i].d=p[i].c=p[i].b;
        dp[i]=1;
    }
    for(int i=1;i<=k;i++){
        cin(xp),cin(t);
        p[xp].c=min(p[xp].c,t);
        p[xp].d=max(p[xp].d,t);
    }
    solve(1,n);
    printf("%d\n",ads);
    return 0;
}

只有30分，问为什么改成：

#include<cstdio>
#include<algorithm>
using namespace std;
int n,k,n_,dp[100001],ads=1,xp,t;
struct value{
    int a,b,c,d;
}p[100001];
int lp[(1<<19)],_n;
inline void cin(int &x){
    x=0;
    bool f=false;
    char c='L';
    while((c<'0'||c>'9')&&c!='-')c=getchar();
    if(c=='-'){
        f=true;
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=x*10+c-'0';
        c=getchar();
    }
    if(f)x=-x;
}
inline void cout(int f){
    if(f<0){
    putchar('-');
    f=-f;
   }
   if(f>=10)cout(f/10);
   putchar(f%10+'0');
}
inline void add(int pl,int val){
    for(int i=pl;i<=n_;i+=(-i)&i){
        lp[i]=max(lp[i],val);
    }
}
inline void deleter(int pl){
    for(int i=pl;i<=n_;i+=(-i)&i){
        lp[i]=0;
    }
}
inline int query(int pl){
    int s=0;
    for(int i=pl;i>0;i&=i-1)s=max(s,lp[i]);
    return s;
}
inline bool cmpa(value x,value y){
    return x.a<y.a;
}
inline bool cmpb(value x,value y){
    if(x.b==y.b)return x.a<y.a;
    else return x.b<y.b;
}
inline bool cmpc(value x,value y){
    if(x.c==y.c)return x.a<y.a;
    else return x.c<y.c;
}
inline void solve(int l,int r){
    if(l==r){ads=max(ads,dp[p[l].a]);return;}
    int mid=(l+r)>>1;
    solve(l,mid);
    sort(p+l,p+mid+1,cmpb);
    sort(p+mid+1,p+r+1,cmpc);
    for(int i=l-1,j=mid+1;j<=r;j++){
        while(i<mid&&p[i+1].b<=p[j].c){i++,add(p[i].d,dp[p[i].a]+1);}
        dp[p[j].a]=max(dp[p[j].a],query(p[j].b));
    }
    for(int i=l;i<=mid&&p[i].b<=p[r].c;i++)deleter(p[i].d);
    sort(p+l,p+r+1,cmpa);
    solve(mid+1,r);
}
int main(){
    cin(n),cin(k);
    n_=1;
    while(n_<100000)n_*=2;
    for(int i=1;i<=n;i++){
        cin(p[i].b);
        p[i].a=i;
        p[i].d=p[i].c=p[i].b;
        dp[i]=1;
    }
    for(int i=1;i<=k;i++){
        cin(xp),cin(t);
        p[xp].c=min(p[xp].c,t);
        p[xp].d=max(p[xp].d,t);
    }
    solve(1,n);
    printf("%d\n",ads);
    return 0;
}

就满分了？