Source Code

Problem: 2528  User: chenxuan123456789 
Memory: N/A  Time: N/A 
Language: C  Result: Runtime Error 

Source Code 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define len 100100
typedef struct node
{
	int lchild;
	int rchild;
	int col;
}Node;
Node a[len*16];
int num[10010][2];
int flag[10010],f[10010],dist[10010],cut,hash,mark[len];
int cmp(const void *_a,const void *_b)
{
	int *a=(int*)_a;
	int *b=(int*)_b;
	return (*a)-(*b);
}
void bulit(int s,int e,int step)
{
	int mid;
	a[step].lchild=s;
	a[step].rchild=e;
	a[step].col=0;
	if(s==e)
	return;
	else
	{
		mid=(s+e)>>1;
		bulit(s,mid,2*step);
		bulit(mid+1,e,2*step+1);
	}
}
void insert(int s,int e,int step,int c)
{
	int mid;
	if(a[step].lchild>=s&&a[step].rchild<=e)
	{
		a[step].col=c;
		return ;
	}
	if(a[step].col)
	{
		a[2*step].col=a[step].col;
		a[2*step+1].col=a[step].col;
		a[step].col=0;
	}
	   mid=(a[step].lchild+a[step].rchild)>>1;
		if(e<=mid)
			insert(s,e,2*step,c);
		else
		if(s>mid)
			insert(s,e,2*step+1,c);
		else
		{
			insert(s,mid,2*step,c);
			insert(mid+1,e,2*step+1,c);
		}
}
void print(int s,int e,int step)
{
	int mid;
	if(s==e)
	{
		printf("%d %d %d %d\n",step,a[step].lchild,a[step].rchild,a[step].col);
		return ;
	}
	else
	{
		mid=(s+e)>>1;
		print(s,mid,2*step);
		print(mid+1,e,2*step+1);
		printf("%d %d %d %d\n",step,a[step].lchild,a[step].rchild,a[step].col);
	}
}
void input(int n)
{
	int i,p=0;
	for(i=1;i<=n;i++)
	{
		scanf("%d %d",&num[i][0],&num[i][1]);
		if(!flag[num[i][0]])
		{
			f[p++]=num[i][0];
			flag[num[i][0]]=1;
		}
		if(!flag[num[i][1]])
		{
			f[p++]=num[i][1];
			flag[num[i][1]]=1;
		}
	}
	qsort(f,p,sizeof(f[0]),cmp);
	hash=1;
	for(i=0;i<p;i++)
	{
		dist[f[i]]=hash++;
	}
	hash--;
	bulit(1,hash,1);
	for(i=1;i<=n;i++)
	insert(dist[num[i][0]],dist[num[i][1]],1,i);
}
void solve(int s,int e,int step)
{
	int mid;
	if(!mark[a[step].col]&&a[step].col!=-1&&a[step].col)
	{
		cut++;
		mark[a[step].col]=1;
		return ;
	}
	if(mark[a[step].col])
	return;
	mid=(s+e)>>1;
    solve(s,mid,2*step);
	solve(mid+1,e,2*step+1);
}
int main()
{
	int c,n;
	scanf("%d",&c);
	while(c--)
	{
		scanf("%d",&n);
		input(n);
		cut=0;
		//print(1,hash,1);
		solve(1,hash,1);
		printf("%d\n",cut);
	}
	return 1;
}
/*
2
5
1 4
2 6
8 10
3 4
7 10
*/