#include<iostream>
#define N 10000
#define MAXINT 10000000
using namespace std;

struct node
{
	int s,e;
	int count;
	int poster;
	node *lchild,*rchild;
};

node* create(node *root,int a,int b)
{
	root=(node*)malloc(sizeof(node));
	root->s=a;
	root->e=b;
	root->count=0;
	root->poster=-1;
	root->lchild=root->rchild=NULL;
	if(b-a==1)
	{
		root->lchild=create(root->lchild,a,(a+b)/2);
		root->rchild=create(root->rchild,(a+b)/2+1,b);
	}
	if(b-a>1)
	{
		root->lchild=create(root->lchild,a,(a+b)/2);
		root->rchild=create(root->rchild,(a+b)/2,b);
	}
	return root;
}

void insert(node *root,int a,int b,int poster)
{
	if(root==NULL) return ;
	int mid=(root->s+root->e)/2;
	if(a<=root->s&&b>=root->e)
	{
		root->count++;
		root->poster=poster;
		insert(root->lchild,a,b,poster);
		insert(root->rchild,a,b,poster);
	}
	else
	{
		if(a<=mid)
		{
			root->poster=-1;
			insert(root->lchild,a,b,poster);
		}
		if(b>=mid)
		{
			root->poster=-1;
			insert(root->rchild,a,b,poster);
		}
	}
}

int find(node *root,int a,int b,int poster)
{
	if(root==NULL) return 0;
	int mid=(root->s+root->e)/2;
	if(root->s<=a&&root->e>=b) 
	{
		if(root->poster!=-1&&root->poster!=poster)
			return 0;
	}
	if(a<=root->s&&b>=root->e&&(root->count>0&&root->poster==poster)) return 1;
	else
	{
		if(a<=mid) return find(root->lchild,a,b,poster);
		if(b>=mid) return find(root->rchild,a,b,poster);	
	}
	return 0;
}

struct line
{
	int x;
	int y;
};

line l[N+1];
node *root;
int n;
int pmax,pmin;

int max(int x,int y)
{
	if(x>y) return x;
	else return y;
}

int min(int x,int y)
{
	if(x<y) return x;
	else return y;
}

void input()
{
	pmax=-10000001;
	pmin=10000001;
	int i,m1,m2;
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&l[i].x,&l[i].y);
		m1=max(l[i].x,l[i].y);
		m2=min(l[i].x,l[i].y);
		if(pmax<m1) pmax=m1;
		if(pmin>m2) pmin=m2;
	}
}	

int main()
{
//	freopen("pku_2528.in","r",stdin);
	int CASE,i;
	scanf("%d",&CASE);
	while(CASE--)
	{
		int count=0;
		scanf("%d",&n);
		input();
		root=create(root,pmin,pmax);
		for(i=1;i<=n;i++)
			insert(root,l[i].x,l[i].y,i);
		for(i=1;i<=n;i++)
			if(find(root,l[i].x,l[i].y,i)) count++;
		printf("%d\n",count);
	}
	return 0;
}

• 要用线段树做的话, 加个离散化吧, 不然坐标的跨越范围大(ex:1 Max)而且N值小的数据很多的话, 会很费时.... (74) qinhanlei 2008-09-02 16:40:11