记录编号	392681	评测结果	A
题目名称	[CEPC2001]水平可见线段	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.107 s
提交时间	2017-04-08 16:30:42	内存使用	1.22 MiB

//KZNS
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;
#define Nmax 8010
class poi { public:
	int l, r, id;
} tr[Nmax*4*2], sgls[Nmax];
void maketree(int x, int l, int r) {
	poi &u = tr[x];
	u.l = l;
	u.r = r;
	u.id = 0;
	if (l < r) {
		int md = (l + r) >> 1;
		maketree(x<<1, l, md);
		maketree(x<<1^1, md+1, r);
	}
}
bool cmp (const poi &a, const poi &b) {
	return a.id < b.id;
}
int N;
vector<int> gp[Nmax];
void cgin(int x, int l, int r, int c) {
	poi &u = tr[x];
	if (l <= u.l && u.r <= r)
		u.id = c;
	else {
		if (u.id > 0) {
			cgin(x<<1, u.l, u.r, u.id);
			cgin(x<<1^1, u.l, u.r, u.id);
		}
		u.id = -1;
		if (l <= tr[x<<1].r)
			cgin(x<<1, l, r, c);
		if (tr[x<<1^1].l <= r)
			cgin(x<<1^1, l, r, c);
	}
}
void adeg(int x, int l, int r, int c) {
	poi &u = tr[x];
	if (u.id > 0) {
		gp[c].push_back(u.id);
		gp[u.id].push_back(c);
	}
	else if (u.id < 0) {
		if (l <= tr[x<<1].r)
			adeg(x<<1, l, r, c);
		if (tr[x<<1^1].l <= r)
			adeg(x<<1^1, l, r, c);
	}
}
void init() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++)
		scanf("%d %d %d", &sgls[i].l, &sgls[i].r, &sgls[i].id);
	sort(sgls+1, sgls+1+N, cmp);
	maketree(1, 0, 16000);
	int a, b;
	for (int i = 1; i <= N; i++) {
		gp[i].clear();
		a = sgls[i].l;
		b = sgls[i].r;
		adeg(1, a*2, b*2, i);
		cgin(1, a*2, b*2, i);
	}
	for (int i = 1; i <= N; i++) {
		if (gp[i].size() == 0)
			continue;
		sort(gp[i].begin(), gp[i].end());
		int k = 0;
		for (int j = 1; j < (int)gp[i].size(); j++) {
			if (gp[i][j] != gp[i][k])
				gp[i][++k] = gp[i][j];
		}
		gp[i].resize(k+1);
	}
}
typedef pair<int, int> pr;
class mminn { public:
	bool operator () (const pr &a, const pr &b) {
		return a.second > b.second;
	}
};
void work() {
	int ans = 0;
	priority_queue<pr, vector<pr>, mminn> ls;
	bool ud[Nmax] = {false};
	bool nu[Nmax] = {false};
	int outd[Nmax];
	for (int i = 1; i <= N; i++)
		ls.push(make_pair(i, outd[i] = gp[i].size()));
	pr u;
	int x, v;
	while (!ls.empty()) {
		u = ls.top();
		ls.pop();
		if (ud[x = u.first])
			continue;
		ud[x] = true;
		for (int i = 0; i < (int)gp[x].size(); i++) {
			v = gp[x][i];
			if (ud[v])
				continue;
			for (int j = 0; j < (int)gp[v].size(); j++)
				if (nu[gp[v][j]])
					ans++;
			nu[v] = true;
			ls.push(make_pair(v, --outd[v]));
		}
		for (int i = 0; i < (int)gp[x].size(); i++)
			nu[gp[x][i]] = false;
	}
	printf("%d\n", ans);
}
int main() {
	freopen("visiblesegments.in", "r", stdin);
	freopen("visiblesegments.out", "w", stdout);
	int T;
	scanf("%d", &T);
	while (T--) {
		init();
		work();
	}
	return 0;
}
//UBWH