2037.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2037 on 2006-03-11 at 12:15:55 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 20480;

class SegTree {
private:
	SegTree *left, *right;
	int x, y, cover;
	void update();
public:
	int len;
	SegTree(int, int);
	~SegTree();
	void insert(int, int);
};
SegTree::SegTree(int l, int r) : x(l), y(r) {
	cover = len = 0;
	if(y == x+1) left = right = NULL;
	else {
		int m = (x + y) / 2;
		left = new SegTree(x, m);
		right = new SegTree(m, y);
	}
}
SegTree::~SegTree() {
	if(left != NULL) delete left;
	if(right != NULL) delete right;
}
void SegTree::update() {
	if(cover > 0) len = y - x;
	else if(y - x == 1) len = 0;
	else len = left->len + right->len;
}
void SegTree::insert(int l, int r) {
	if(l <= x && y <= r) cover++;
	else {
		if(l < (x + y) / 2) left->insert(l, r);
		if(r > (x + y) / 2) right->insert(l, r);
	}
	update();
}

int dispart(int*, int);

int main()
{
	int x[MAX], n;
	int t, T, i;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d", &n);
		for(i = 0; i < n; i++) scanf("%d %d", &x[2*i], &x[2*i+1]);
		SegTree st(0, dispart(x, 2*n));
		int visible = 0;
		for(i = n-1; i >= 0; i--) {
			int pcl = st.len;
			st.insert(x[2*i], x[2*i+1]+1);
			if(pcl != st.len) visible++;
		}
		printf("%d\n", visible);
	}
	
	return 0;
}

int dispart(int* src, int n)
{
	int i, dn = 0, dis[MAX];
	for(i = 0; i < n; i++) dis[i] = src[i];
	sort(dis, dis+n);
	for(i = 0; i < n; i++)
		if(i == 0 || dis[i] != dis[i-1]) dis[dn++] = dis[i];
	for(i = 0; i < n; i++) src[i] = lower_bound(dis, dis+dn, src[i]) - dis;
	return dn;
}