学步园

做法：抄hh大神的，可是，有些地方自己的小聪明导致了错误，记录一下

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#define left l,m,x<<1
#define right m+1,r,x<<1|1
#define LMT 40002
//出了map,set,另外的能用数组就用数组
//应不应该加点，这个需要考虑，很多情况不需要加点的。
using namespace std;
struct line
{
    int l,r,lx,rx;
}paper[10002];
int vx[LMT],num;
bool see[LMT];
int add[LMT<<2],ans;
void cut(int x)
{
    if(add[x]!=-1)
    {
        add[x<<1]=add[x<<1|1]=add[x];
        add[x]=-1;
    }
}
void update(int L,int R,int key,int l,int r,int x)
{
    if(L<=l&&r<=R)
    {
        add[x]=key;
        return;
    }
    cut(x);
    int m=(l+r)>>1;
    if(L<=m)update(L,R,key,left);
    if(R>m)update(L,R,key,right);
}
void equery(int l,int r,int x)
{
    if(l==r)
    {
        if(add[x]!=-1&&see[add[x]]==0)
        {
            see[add[x]]=1;
            ans++;
        }
        return ;
    }
    cut(x);
    int m=(l+r)>>1;
    equery(left);
    equery(right);
}
int bin(int x)
{
    int m,l=0,r=num-1;
    while(l<=r)
    {
        m=(l+r)>>1;
        if(x==vx[m])return m;
        if(x>vx[m])l=m+1;
        else r=m-1;
    }
    return -1;
}
int main()
{
    int T,n,k,end;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
         num=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&paper[i].lx,&paper[i].rx);
            vx[num++]=paper[i].lx;
            vx[num++]=paper[i].rx;
        }
        sort(vx,vx+num);
        k=1;
        for(int i=1;i<num;i++)
        if(vx[i]!=vx[i-1])vx[k++]=vx[i];//这一步省不得，会导致没来已经覆盖的被判为不覆盖
        end=num=k;
        for(int i=1;i<end;i++)
            if(vx[i]-vx[i-1]>1)vx[num++]=vx[i-1]+1;
        sort(vx,vx+num);
        for(int i=0;i<n;i++)
        {
            paper[i].l=bin(paper[i].lx);
            paper[i].r=bin(paper[i].rx);
        }
        end=num;
        memset(add,-1,sizeof(add));
        memset(see,0,sizeof(see));
        for(int i=0;i<n;i++)
            update(paper[i].l,paper[i].r,i,0,end-1,1);
        ans=0;
        equery(0,end-1,1);
        printf("%d\n",ans);
    }
    return 0;
}