#include <iostream>
using namespace std;

const int MAX_N = 10000;
int N;
int A[MAX_N+5], B[MAX_N+5];

struct Node
{
	int left;
	int right;
	bool covered;
	Node *lc;
	Node *rc;

} tree[MAX_N*6];

bool insert(int root, int l, int r)
{
	if(tree[root].covered)  return false;

	if(l==tree[root].left && tree[root].right==r && tree[root].lc==NULL)
	{
		tree[root].covered = true;
		return true;
	}
	
	int child = root<<1;
	if(tree[root].lc == NULL)//如果当前区间么有被分割，则分割区间
	{
		tree[root].lc = &tree[child];
		tree[root].rc = &tree[child+1];

		tree[child].covered = false;
		tree[child].lc = tree[child].rc = NULL;

		tree[child+1].covered = false;
		tree[child+1].lc = tree[child].rc = NULL;
		if(r == tree[root].right)
		{
			tree[child].left = tree[root].left;
			tree[child].right = l-1;

			tree[child+1].left = l;
			tree[child+1].right = r;

			return insert(child+1, l, r);
		}
		if(l == tree[root].left)
		{
			tree[child].left = l;
			tree[child].right = r;

			tree[child+1].left = r+1;
			tree[child+1].right = tree[root].right;

			return insert(child, l, r);
		}
		tree[child].left = tree[root].left;
		tree[child].right = r;

		tree[child+1].left = r+1;
		tree[child+1].right = tree[root].right;
		return insert(child, l, r);
	}

	int mid = tree[child].right;
	if(r <= mid)
		return insert(child, l, r);
	if(l > mid)
		return insert(child+1, l, r);
	
	return insert(child, l, mid) || insert(child+1, mid+1, r);
}

int main()
{
	int T, i, ans;
	scanf("%d", &T);
	tree[1].left = 1;
	tree[1].right = 10000000;
	while(T--)
	{
		ans = 0;
		tree[1].covered = false;
		tree[1].lc = tree[1].rc = NULL;
		scanf("%d", &N);
		for(i=1; i<=N; i++)
			scanf("%d%d", A+i, B+i);
		for(i=N; i>=1; i--)
		{
			if(insert(1, A[i], B[i]))
				ans++;    
		}
		printf("%d\n", ans);
	}    
	return 0;
}

• Re:请教：为什么全是 RE，论坛里的数据都过了！！！！ (6) Euler_M 2011-03-27 11:37:25