记录编号	192014	评测结果	A
题目名称	[CEPC2001]水平可见线段	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.166 s
提交时间	2015-10-09 17:14:04	内存使用	0.90 MiB

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<deque>
#include<set>
using namespace std;
const int SIZEN=8010;
int d;
int N,ma;
int co[SIZEN*10];
set<int> c[SIZEN];
set<pair<int,int> > seg;
set<int>::iterator key;
class miku
{
public:
	int yd,yu,x;
}L[SIZEN];
bool cmp(miku a,miku b)
{
	if(a.x==b.x) return a.yd<b.yd;
	return a.x<b.x;
}
void read()
{
	ma=0;
	scanf("%d",&N);
	for(int i=0;i<=N;i++) c[i].clear();
	for(int i=1;i<=N;i++)
	{
		scanf("%d%d%d",&L[i].yd,&L[i].yu,&L[i].x);
		if(L[i].yu>ma) ma=L[i].yu;
	}
	sort(L+1,L+1+N,cmp);
}
void adds(int x,int to)
{
	//if(c[x].count(to)>0) return;
	c[x].insert(to);
	c[to].insert(x);
}
void merge(int root,int x,int y)
{
	if(x==y) co[root]=x;
	else co[root]=-1;
}
void add(int root,int l,int r,int x,int yd,int yu,int now)
{
	if(now>0) co[root]=now;
	if(l>yu||r<yd) return;
	if(yd<=l&&yu>=r&&co[root]!=-1)
	{
		if(co[root]!=0) adds(x,co[root]);
		co[root]=x;
		return;
	}
	int mid=(l+r)/2;
	add(root<<1,l,mid,x,yd,yu,co[root]);
	add(root<<1|1,mid+1,r,x,yd,yu,co[root]);
	merge(root,co[root<<1],co[root<<1|1]);
}
void gragh()
{
	memset(co,0,sizeof(co));
	for(int i=1;i<=N;i++) add(1,0,2*ma,i,2*L[i].yd,2*L[i].yu,0);
}
void check_s()
{
	for(int i=1;i<=N;i++)
	{
		cout<<i<<endl;
		for(key=c[i].begin();key!=c[i].end();key++)
			cout<<*key<<" ";
		cout<<endl;
	}
}
bool connect(int x,int y)
{
	if(c[x].count(y)>0) return 1;
	return 0;
}
void Delet(int x,int y)
{
	seg.erase(seg.find(make_pair(c[x].size(),x)));
	seg.erase(seg.find(make_pair(c[y].size(),y)));
	c[x].erase(c[x].find(y));
	c[y].erase(c[y].find(x));
	seg.insert(make_pair(c[x].size(),x));
	seg.insert(make_pair(c[y].size(),y));
}
void work()
{
	int ans=0;
	seg.clear();
	set<pair<int,int> >::iterator it;
	pair<int,int> P;
	deque<int> S;
	for(int i=1;i<=N;i++)
	{
		P.first=c[i].size();
		P.second=i;
		seg.insert(P);
	}
	for(int i=1;i<=N;i++)
	{
		S.clear();
		it=seg.begin();
		P=*it;
		int x=P.second;
		for(key=c[x].begin();key!=c[x].end();key++) S.push_back(*key);
		for(int j=0;j<S.size();j++)
		{
            for(int k=j+1;k<S.size();k++)
			{	
				if(connect(S[j],S[k])) ans++;
			}
		}
        for(int j=0;j<S.size();j++) 
		{
			//cout<<"arrive"<<endl;
			//cout<<x<<" "<<S[j]<<endl;
			Delet(x,S[j]);
			//cout<<"arrive2"<<endl;
		}
		//cout<<"arrive3"<<endl;
        seg.erase(seg.begin());	
		//cout<<"arrive4"<<endl;
	}
	printf("%d\n",ans);
}
int main()
{
	freopen("visiblesegments.in","r",stdin);
	freopen("visiblesegments.out","w",stdout);
	scanf("%d",&d);
	while(d)
	{
		d--;
		read();
		gragh();
		//check_s();
		//cout<<"*********"<<endl;
		work();
	}
	return 0;
}