记录编号	191987	评测结果	E
题目名称	1549.[CEPC2001]水平可见线段	最终得分	0
用户昵称	mikumikumi	是否通过	未通过
代码语言	C++	运行时间	0.074 s
提交时间	2015-10-09 15:12:52	内存使用	5.27 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];
deque<int> s[SIZEN];
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=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)
{
	for(int i=0;i<s[x].size();i++)
		if(s[x][i]==to) return;
	s[x].push_back(to);
	s[to].push_back(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]==0) co[root]=now;
	if(l!=r&&co[root]==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(int j=0;j<s[i].size();j++)
			cout<<s[i][j]<<" ";
		cout<<endl;
	}
}
bool connect(int x,int y)
{
	for(int i=0;i<s[x].size();i++)
		if(s[x][i]==y) return 1;
	return 0;
}
void Delet(int x)
{
	for(int i=0;i<s[x].size();i++)
	{
		int v=s[x][i];
		s[v].erase(find(s[v].begin(),s[v].end(),x));
	}
}
void work()
{
	int ans=0;
	set<pair<int,int> > seg;
	set<pair<int,int> >::iterator it;
	pair<int,int> P;
	for(int i=1;i<=N;i++)
	{
		P.first=s[i].size();
		P.second=i;
		seg.insert(P);
	}
	for(it=seg.begin();it!=seg.end();it++)
	{
		P=*it;
		int x=P.second;
		//cout<<x<<endl;
		for(int j=0;j<s[x].size();j++)
		{
			for(int k=j+1;k<s[x].size();k++)
			{
				//cout<<s[x][j]<<" "<<s[x][k]<<endl;
				if(connect(s[x][j],s[x][k])) ans++;
			}
		}
		Delet(P.second);
	}
	printf("%d",ans);
}
int main()
{
	freopen("visiblesegments.in","r",stdin);
	freopen("visiblesegments.out","w",stdout);
	scanf("%d",&d);
	while(d)
	{
		d--;
		read();
		gragh();
		//check_s();
		work();
	}
	return 0;
}