pku2528 Mayor's posters

又一道线段树

#include <cstdio>
#include <cstring>
#include <algorithm>
using std::sort;
const int size = 10000000 + 5, maxn = (10000 + 5) * 2;
int n, p[maxn * 2], lp, hash[size];
struct seg_t {
	int li, ri;
} seg[maxn];

int A, B, color, tree[maxn * 2 * 3];
bool exist[maxn];
void add(int low, int high, int node)
{
	if (A <= low && high <= B) {
		tree[node] = color;
	} else if (low <= B && A <= high) {
		if (tree[node] != -1)
			tree[node * 2] = tree[node * 2 + 1] = tree[node];
		int mid = (low + high) / 2;
		add(low, mid, node * 2);
		add(mid + 1, high, node * 2 + 1);
		if (tree[node * 2] == tree[node * 2 + 1])
			tree[node] = tree[node * 2];
		else
			tree[node] = -1;
	}
}

int query(int low, int high, int node)
{
	if (A <= low && high <= B && tree[node] != -1) {
		if (!exist[tree[node]])
		{
			exist[tree[node]] = true;
			return 1;
		}
	} else if (low <= B && A <= high && low < high) {
		int mid = (low + high) / 2;
		return query(low, mid, node * 2) + query(mid + 1, high, node * 2 + 1);
	}
	return 0;
}

int main()
{
	int tcs;
	scanf("%d", &tcs);
	while (tcs--)
	{
		scanf("%d", &n);
		lp = 0;
		for (int i = 1; i <= n; ++i)
		{
			scanf("%d%d", &seg[i].li, &seg[i].ri);
			p[lp++] = seg[i].li;
			p[lp++] = seg[i].ri;
		}
		
		sort(p, p + lp);
		int cnt = 1, left, right;
		left = hash[p[0]] = cnt;
		for (int i = 1; i < lp; ++i)
		{
			if (p[i] == p[i - 1])
				continue;
			else {
				if (p[i - 1] + 1 < p[i])
					++cnt;
				hash[p[i]] = ++cnt;
			}
		}
		right = hash[p[lp - 1]];
		
		memset(tree, 0xff, sizeof(tree));
		for (int i = 1; i <= n; ++i)
		{
			A = hash[seg[i].li], B = hash[seg[i].ri];
			color = i;
			add(left, right, 1);
		}
		
		memset(exist, false, sizeof(exist));
		A = left, B = right;
		printf("%d\n", query(left, right, 1));
	}
	return 0;
}