1784.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/* This Code is Submitted by wywcgs for Problem 1784 on 2007-05-05 at 19:40:37 */
#include <cstdio>
#include <stack>
#include <set>
#include <algorithm>
using namespace std;

const int N = 8100;

set<int> g[N];

class Segment {
public:
	int y1, y2, x;
	void make() { scanf("%d %d %d", &y1, &y2, &x); }
	bool operator<(const Segment& s) const { return x < s.x; }
};

class SegTree {
private:
	SegTree *left, *right;
	int x, y, cov;
public:
	SegTree(int, int);
	~SegTree() { if(y-x != 1) { delete left; delete right; } }
	void insert(int, int, int);
};
SegTree::SegTree(int b, int e) : left(NULL), right(NULL), x(b), y(e), cov(-1) {
	if(y-x == 1) return;
	int mid = (y+x)>>1;
	left = new SegTree(x, mid);
	right = new SegTree(mid, y);
}
void SegTree::insert(int px, int py, int sn) {
	if(px <= x && py >= y && cov != -2) {
		if(cov != -1 && !g[cov].count(sn)) { g[cov].insert(sn); g[sn].insert(cov); }
		cov = sn;
	} else {
		int mid = (x+y)>>1;
		if(cov != -2) left->cov = right->cov = cov;
		if(px < mid) left->insert(px, py, sn);
		if(py > mid) right->insert(px, py, sn);
		if(left->cov == -2 || right->cov == -2 || left->cov != right->cov) cov = -2;
		else cov = left->cov;
	}
}

int main()
{
	int T, y[2*N], d[N];
	Segment s[N];
	bool vst[N];
	
	scanf("%d", &T);
	for(int t = 0; t < T; t++) {
		int n; scanf("%d", &n);
		for(int i = 0; i < n; i++) 
			{ s[i].make(); g[i].clear(); y[2*i] = s[i].y1; y[2*i+1] = s[i].y2; }
		sort(s, s+n); sort(y, y+2*n);
		int dn = unique(y, y+2*n)-y;
		SegTree *root = new SegTree(0, 2*dn);
		for(int i = 0; i < n; i++) {
			int a = lower_bound(y, y+dn, s[i].y1)-y, 
				b = lower_bound(y, y+dn, s[i].y2)-y;
			root->insert(2*a, 2*b+1, i);
		}
		memset(vst, false, sizeof(vst));
		stack<int> stk;
		for(int i = 0; i < n; i++)
			if(g[i].size() <= 5) stk.push(i);
		int res = 0;
		while(!stk.empty()) {
			int p = stk.top(); stk.pop();
			if(vst[p]) continue;
			vst[p] = true;
			for(set<int>::iterator it = g[p].begin(); it != g[p].end(); it++) {
				set<int>::iterator ip = it;
				for(ip++; ip != g[p].end(); ip++)
					if(g[*it].count(*ip)) res++;
				g[*it].erase(p);
				if(g[*it].size() <= 5) stk.push(*it);
			}
		}
		printf("%d\n", res);
		delete root;
	}
	return 0;
}