按照输入次序进行覆盖，求最上面能看到多少种不同的海报，一看就是线段树加离散化，不过这里的离散化需要注意

例如 测试用例的为

3

1  9

1  3

6  9

这样的话普通的离散化  如下

1  2  3  4

1  3  6  9

上面对应离散化编号，下面则是实际的值，这样的话普通离散化算出的答案是2，而正确的答案是3

所以  针对这种情况，我们约定：当离散化后的相邻点的坐标差大于1时，在这两个离散点之间，插入两坐标之间的任意的一个值。

对于上述测试用例，按约定的离散化可得，

1  2  3  4  5  6  7

1  2  3  4  6  7  9

这样进行离散化得到的答案就为3，代码如下

/*Problem: 2528        User: 96655Memory: 1368K        Time: 94MSLanguage: G++        Result: Accepted*/#include
      
       #include
       
        #include
        
         #include
         
          #include 
          
           #include
           
            using namespace std;const int maxn=40005;short a[maxn<<2],ans;bool b[maxn<<2],xx[10005];struct Q{ int l,r;} q[10005];int y[maxn];void pushdown(int rt){ if(b[rt]) { b[rt*2]=b[rt*2+1]=1; a[rt*2]=a[rt*2+1]=a[rt]; b[rt]=0; }}void update(int rt,int l,int r,int x,int y,int c){ if(x<=l&&r<=y) { a[rt]=c; b[rt]=1; return; } int m=(l+r)>>1; pushdown(rt); if(x<=m)update(rt*2,l,m,x,y,c); if(y>m)update(rt*2+1,m+1,r,x,y,c);}void query(int rt,int l,int r){ if(l==r) { if(a[rt]==-1)return; if(!xx[a[rt]]) ++ans,xx[a[rt]]=1; return; } int m=(l+r)>>1; pushdown(rt); query(rt*2,l,m); query(rt*2+1,m+1,r);}int main(){ int T; scanf("%d",&T); while(T--) { int n,cnt=0,d=1; ans=0; scanf("%d",&n); for(int i=1; i<=n; ++i) { scanf("%d%d",&q[i].l,&q[i].r); y[cnt++]=q[i].l; y[cnt++]=q[i].r; } sort(y,y+cnt); for(int i=1; i
            
             0; --i) if(y[i]-1>y[i-1])y[d++]=y[i]-1; sort(y,y+d); memset(a,-1,sizeof(a)); memset(b,0,sizeof(b)); memset(xx,0,sizeof(xx)); for(int i=1; i<=n; ++i) { q[i].l=lower_bound(y,y+d,q[i].l)-y; ++q[i].l; q[i].r=lower_bound(y,y+d,q[i].r)-y; ++q[i].r; update(1,1,d,q[i].l,q[i].r,i); } query(1,1,d); printf("%d\n",ans); } return 0;}