#include<bits/stdc++.h>
using namespace std;
int N,M;
int A[1005],B[1005];
int T[2005],cnt=0;
map<int,int> MAP;
int sum[32005];
bool tag[32005];

void pushup(int rt){
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}

void pushdown(int rt,int ls,int rs){
    if(tag[rt]==false) return;
    sum[rt<<1]=ls;
    sum[rt<<1|1]=rs;
    tag[rt<<1]=true;
    tag[rt<<1|1]=true;
    tag[rt]=false;
}

void upd(int rt,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
       sum[rt]=r-l+1;
       tag[rt]=true;
       return;
    }
    int mid=l+r>>1;
    pushdown(rt,mid-l+1,r-mid);
    if(ql<=mid) upd(rt<<1,l,mid,ql,qr);
    if(qr>mid) upd(rt<<1|1,mid+1,r,ql,qr);
    pushup(rt);
}

int query(int rt,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
        return sum[rt];
    }
    int mid=l+r>>1,ans=0;
    pushdown(rt,mid-l+1,r-mid);
    if(ql<=mid) ans+=query(rt<<1,l,mid,ql,qr);
    if(qr>mid) ans+=query(rt<<1|1,mid+1,r,ql,qr);
    return ans;
}

int main(){
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    cin>>N>>M;
    for(int i=1;i<=M;i++){
        cin>>A[i]>>B[i];
        T[++cnt] = A[i];
        T[++cnt] = B[i];
    }

    sort(T+1, T+cnt+1);
    int len = unique(T+1, T+cnt+1) - (T+1);
    //cout<<len<<endl;
    MAP[T[1]] = 1;
    for(int i=2;i<=len;i++){
        if(T[i] - T[i-1] == 1) MAP[T[i]] = MAP[T[i-1]] + 1;
        else MAP[T[i]] = MAP[T[i-1]] + 2;
    }

    for(int i=1;i<=M;i++){
        A[i] = MAP[A[i]];
        B[i] = MAP[B[i]];
    }

    int ans=0;
    for(int i=M;i>=1;i--){
        if(query(1,1,32000,A[i],B[i]) != B[i] - A[i] + 1){
            ans++;
            upd(1,1,32000,A[i],B[i]);
        }
    }
    cout<<ans;
    return 0;
}

这份代码WA了最后一个点 #12

但仅仅将T数组的空间调节至2785

如下：

#include<bits/stdc++.h>
using namespace std;
int N,M;
int A[1005],B[1005];
int T[2785],cnt=0;
map<int,int> MAP;
int sum[32005];
bool tag[32005];

void pushup(int rt){
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}

void pushdown(int rt,int ls,int rs){
    if(tag[rt]==false) return;
    sum[rt<<1]=ls;
    sum[rt<<1|1]=rs;
    tag[rt<<1]=true;
    tag[rt<<1|1]=true;
    tag[rt]=false;
}

void upd(int rt,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
       sum[rt]=r-l+1;
       tag[rt]=true;
       return;
    }
    int mid=l+r>>1;
    pushdown(rt,mid-l+1,r-mid);
    if(ql<=mid) upd(rt<<1,l,mid,ql,qr);
    if(qr>mid) upd(rt<<1|1,mid+1,r,ql,qr);
    pushup(rt);
}

int query(int rt,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
        return sum[rt];
    }
    int mid=l+r>>1,ans=0;
    pushdown(rt,mid-l+1,r-mid);
    if(ql<=mid) ans+=query(rt<<1,l,mid,ql,qr);
    if(qr>mid) ans+=query(rt<<1|1,mid+1,r,ql,qr);
    return ans;
}

int main(){
    //freopen("a.in","r",stdin);
   // freopen("a.out","w",stdout);
    cin>>N>>M;
    for(int i=1;i<=M;i++){
        cin>>A[i]>>B[i];
        T[++cnt] = A[i];
        T[++cnt] = B[i];
    }

    sort(T+1, T+cnt+1);
    int len = unique(T+1, T+cnt+1) - (T+1);
    //cout<<len<<endl;
    MAP[T[1]] = 1;
    for(int i=2;i<=len;i++){
        if(T[i] - T[i-1] == 1) MAP[T[i]] = MAP[T[i-1]] + 1;
        else MAP[T[i]] = MAP[T[i-1]] + 2;
    }

    for(int i=1;i<=M;i++){
        A[i] = MAP[A[i]];
        B[i] = MAP[B[i]];
    }

    int ans=0;
    for(int i=M;i>=1;i--){
        if(query(1,1,32000,A[i],B[i]) != B[i] - A[i] + 1){
            ans++;
            upd(1,1,32000,A[i],B[i]);
        }
    }
    cout<<ans;
    return 0;
}

就可以AC

其中T数组是我开的一个用于离散化的临时数组，我认为只需开两倍M的空间就够了呀......

有没有大佬来解释一下，谢谢！