pku2528.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <stdlib.h>
#define SZ 100010

typedef struct 
{
	int l;
	int m;
	int r;
	int s;
} Node;

typedef struct 
{
	int l, r;
} Edge;

Node nd[SZ * 2];
Edge e[SZ];

int node_sum;

int a[SZ * 2], b[SZ * 2];

int cp(const void *a, const void *b)
{
	return *(int *)a - *(int *)b;
}

void Creat(int s, int l, int r)
{
	int m;
	if (node_sum < s)
	{
		node_sum = s;
	}
	m = (l + r) / 2;
	nd[s].l = a[l];
	nd[s].r = a[r];
	nd[s].m = a[m];
	nd[s].s = 0;

	if (l < r)
	{
		Creat(s * 2, l, m);
		Creat(s * 2 + 1, m + 1, r);
	}
}

int Insert(int s, int l, int r)
{
	int ll, rr;
	ll = 0;
	rr = 0;
	if (s > node_sum)
	{
		return 0;
	}
	if (nd[s].s == 1)
	{
		return 0;
	}
	if (l <= nd[s].l && r >= nd[s].r)
	{
		nd[s].s = 1;
		return 1;
	}
	if (r <= nd[s].m)
	{
		ll = Insert(s * 2, l, r);
	}
	else if (l > nd[s].m)
	{
		rr = Insert(s * 2 + 1, l, r);
	}
	else
	{
		ll = Insert(s * 2, l, r);
		rr = Insert(s * 2 + 1, l, r);
	}
	if (s * 2 < node_sum && nd[2 * s].s && nd[2 * s + 1].s)
	{
		nd[s].s = 1;
	}
	return ll || rr;
}

int main()
{
	int T, n, i, siz, cnt;
	scanf("%d", &T);
	while (T--)
	{
		node_sum = 0;
		scanf("%d", &n);
		for (i = 0; i < n; i++)
		{
			scanf("%d %d", &e[i].l, &e[i].r);
			b[2 * i] = e[i].l;
			b[2 * i + 1] = e[i].r;
		}
		qsort(b, 2 * n, sizeof(b[0]), cp);
		siz = 1;
		a[0] = b[0];
		for (i = 1; i < 2 * n; i++)
		{
			if (b[i] != b[i - 1])
			{
				a[siz++] = b[i];
			}
		}
		Creat(1, 0, siz - 1);

		for (i = siz - 1, cnt = 0; i >= 0; i--)
		{
			cnt += Insert(1, e[i].l, e[i].r);
		}
		printf("%d\n", cnt);
	}
	return 0;
}