#include <cstdio>
#include <algorithm>

using namespace std;

int poster_x[10040];
int poster_y[10040];
int n;
int point[40040];
char flag[10040];
int tot;
int begin[80040];
int end[80040];
int lc[80040];
int rc[80040];
char color[80040];
char needclear[80040];

void MakeTree(int x, int y)
{
	++tot;
	int v = tot;
	begin[v] = point[x];
	end[v] = point[y];
	color[v] = 0;
	needclear[v] = 0;
	if(x + 1 == y)
	{
		lc[v] = 0;
		rc[v] = 0;
	}
	else
	{
		lc[v] = tot + 1;
		MakeTree(x, (x + y) / 2);
		rc[v] = tot + 1;
		MakeTree((x + y) / 2, y);
	}
}

void clear(int num)
{
	needclear[num] = 0;
	if(lc[num] != 0) // internal node
	{
		color[lc[num]] = color[num];
		color[rc[num]] = color[num];
		needclear[lc[num]] = 1;
		needclear[rc[num]] = 1;
	}
}

void Insert(int x, int y, int c, int num)
{
	if(needclear[num])
		clear(num);

	if(begin[num] >= x && end[num] <= y)
	{
		color[num] = c;
		clear(num);
	}
	else
	{
		if(color[num] != c)
		{
			color[num] = -1;
			if(x < end[lc[num]])
				Insert(x, y, c, lc[num]);
			if(y > begin[rc[num]])
				Insert(x, y, c, rc[num]);
		}
	}
}

void Query(int num)
{
	if(needclear[num])
		clear(num);
	if(color[num] >= 0)
		flag[color[num]] = 1;
	else
	{
		Query(lc[num]);
		Query(rc[num]);
	}
}

int main(void)
{
	int c;
	scanf("%d", &c);

	while(c--)
	{
		scanf("%d", &n);
		for(int i = 0; i < n; ++i)
		{
			scanf("%d%d", &poster_x[i], &poster_y[i]);
			point[2 * i] = --poster_x[i];
			point[2 * i + 1] = poster_y[i];
		}
		sort(point, point + 2 * n);

		int pos = 1;
		for(int i = 1; i < 2 * n; ++i)
		{
			if(point[i] != point[pos - 1])
				point[pos++] = point[i];
		}

		tot = 0;
		MakeTree(0, pos-1);
		for(int i = 0; i < n; ++i)
		{
			Insert(poster_x[i], poster_y[i], i + 1, 1);
		}

		memset(flag, 0, sizeof(char) * (n + 1));

		Query(1);
		int sum = 0;
		for(int i = 1; i <= n; ++i)
			sum += flag[i];
		printf("%d\n", sum);
	}
}

• Re:求测试数据，WA到死。。。（付线段树代码） (2290) newpoo 2008-02-29 11:30:45