1 //Accepted    1960K    110MS  2 //线段树+离散化  3 //把所有的坐标排序，从小到大编号，建立线段树  4 #include <cstdio>  5 #include <cstring>  6 #include <iostream>  7 #include <queue>  8 #include <cmath>  9 #include <algorithm> 10 using namespace std; 11 /** 12   * This is a documentation comment block 13   * 如果有一天你坚持不下去了，就想想你为什么走到这儿！ 14   * @authr songt 15   */ 16 const int imax_n = 100005; 17 struct node 18 { 19     int l,r; 20     int change; 21 }f[imax_n*3]; 22 struct item 23 { 24     int coord; 25     int tid; 26     int from; 27 }poster[imax_n*2]; 28 int mark[imax_n*2]; 29 int ans; 30 int n; 31 int cmp(struct item x,struct item y) 32 { 33     return x.coord<y.coord; 34 } 35 int cmp2(struct item x,struct item y) 36 { 37     return x.from<y.from; 38 } 39 void build(int t,int l,int r) 40 { 41     f[t].l=l; 42     f[t].r=r; 43     f[t].change=0; 44     if (l==r) return ; 45     int mid=(f[t].l+f[t].r)/2; 46     build(2*t,l,mid); 47     build(2*t+1,mid+1,r); 48 } 49 void update(int t,int l,int r,int c) 50 { 51     if (f[t].l==l && f[t].r==r) 52     { 53         f[t].change=c; 54         return ; 55     } 56     if (f[t].change!=0) 57     { 58         f[2*t].change=f[2*t+1].change=f[t].change; 59         f[t].change=0; 60     } 61     int mid=(f[t].l+f[t].r)/2; 62     if (r<=mid) update(2*t,l,r,c); 63     else 64     { 65         if (l>mid) update(2*t+1,l,r,c); 66         else 67         { 68             update(2*t,l,mid,c); 69             update(2*t+1,mid+1,r,c); 70         } 71     } 72 } 73 void query(int t,int l,int r) 74 { 75     if (l==r) 76     { 77         if (mark[f[t].change]==0) 78         { 79             ans++; 80             mark[f[t].change]=1; 81         } 82         return ; 83     } 84     int temp=f[t].change; 85     if (temp!=0) 86     { 87         if (mark[temp]==0) 88         { 89             ans++; 90             mark[temp]=1; 91         } 92         return ; 93     } 94     int mid=(f[t].l+f[t].r)/2; 95     query(2*t,l,mid); 96     query(2*t+1,mid+1,r); 97 } 98 int main() 99 {100     int T;101     scanf("%d",&T);102     while (T--)103     {104         scanf("%d",&n);105         for (int i=1;i<=n;i++)106         {107             scanf("%d%d",&poster[2*i-1].coord,&poster[2*i].coord);108             poster[2*i-1].from=poster[2*i].from=i;109         }110         sort(poster+1,poster+2*n+1,cmp);111         int k=0;112         int temp=0;113         int i=1;114         while (i<=2*n)115         {116             if (poster[i].coord==temp)117             {118                 poster[i].tid=k;119             }120             else121             {122                 poster[i].tid=++k;123                 temp=poster[i].coord;124             }125             i++;126         }127         sort(poster+1,poster+2*n+1,cmp2);128         //printf("k=%d\n",k);129        // for (int i=1;i<=2*n;i++)130         //{131         //    printf("coord=%d tid=%d\n",poster[i].coord,poster[i].tid);132         //}133         build(1,1,k);134         //printf("build\n");135         //int kind=1;136         for (int i=1;i<=n;i++)137         {138             int x=poster[2*i-1].tid;139             int y=poster[2*i].tid;140             if (x>y)141             {142                 int t=x;143                 x=y;144                 y=t;145             }146             update(1,x,y,i);147         }148         //printf("update\n");149         ans=0;150         memset(mark,0,sizeof(mark));151         query(1,1,k);152         //for (int i=1;i<=k;i++)153         //printf("%d ",mark[i]);154         //printf("\n");155         printf("%d\n",ans);156     }157     return 0;158 }