果的线段树，结合离散化
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct node
{
int l, r, color;
}tree[80010];
int n;
int x[10010], y[10010], t[10000010];
int point[20010], v[10010];
int cmp(const void *a, const void *b)
{
return *(int *)a-*(int *)b;
}
void build(int l, int r, int p)
{
tree[p].l= l;
tree[p].r= r;
tree[p].color= 0;
if ( l < r )
{
int mid=(l+r)>>1;
build(l, mid, 2*p);
build(mid+1, r, 2*p+1);
}
}
void insert(int l , int r , int p, int color)
{
if ( tree[p].l == l && tree[p].r == r)
{
tree[p].color=color;
return;
}
if (tree[p].color)
{
tree[2*p].color= tree[2*p+1].color=tree[p].color;
tree[p].color=0;
}
int mid= (tree[p].l+tree[p].r)>>1;
if (r <= mid) insert(l, r, 2*p, color);
else if (l > mid) insert(l, r, 2*p+1, color);
else
{
insert(l, mid, 2*p, color);
insert(mid+1, r, 2*p+1, color);
}
}
void find(int l, int r, int p)
{
if (tree[p].color)
{
v[tree[p].color]=1;
return;
}
int mid= (tree[p].l+tree[p].r)>>1;
find(l, mid, 2*p);
find(mid+1, r, 2*p+1);
}
int c;
int main()
{
scanf("%d", &c);
while ( c-- )
{
scanf("%d", &n);
memset(t, 0, sizeof(t));
int i, k=0;
for ( i = 1; i <= n; i++ )
{
scanf("%d%d", x+i, y+i);
if ( !t[x[i]] )
{
t[x[i]]=1;
point[++k]=x[i];
}
if ( !t[y[i]] )
{
t[y[i]]=1;
point[++k]=y[i];
}
}
qsort( point+1, k, sizeof(int), cmp );
for( i= 1; i <= k; i++)
t[point[i]]=i;
build(1, k, 1);
for ( i = 1; i <= n; i++)
{
insert(t[x[i]], t[y[i]], 1, i);
}
memset(v, 0, sizeof(v));
find(1, k ,1);
int sum=0;
for ( i = 1; i <=n ; i++)
if(v[i]) sum++;
printf("%d\n", sum);
}
return 0;
}