记录编号	92402	评测结果	A
题目名称	[CEPC2001]水平可见线段	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.206 s
提交时间	2014-03-20 16:52:28	内存使用	1.92 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
using namespace std;
const int SIZEN=8100;//线段数量,坐标范围
class NODE{//线段树的节点
public:
	int left,right;
	int lc,rc;
	int cover;//-1代表未覆盖
}tree[SIZEN*8];
int tot=0;
void update(int root){
	NODE &now=tree[root];
	if(now.left!=now.right){
		NODE &lson=tree[now.lc],&rson=tree[now.rc];
		if(lson.cover==rson.cover) now.cover=lson.cover;//两个都是-1也会导致是-1......
		else now.cover=-1;
	}
}
void pushdown(int root){
	NODE &now=tree[root];
	if(now.cover==-1) return;
	if(now.left==now.right) return;
	NODE &lson=tree[now.lc],&rson=tree[now.rc];
	lson.cover=rson.cover=now.cover;
}
int build(int x,int y){
	int p=tot++;
	NODE &now=tree[p];
	now.left=x,now.right=y;
	if(x<y){
		int mid=(x+y)>>1;
		now.lc=build(x,mid);
		now.rc=build(mid+1,y);
	}
	else now.cover=0;
	update(p);
	return p;
}
class SEGMENT{
public:
	int y1,y2;
	int x;
};
bool operator < (SEGMENT a,SEGMENT b){
	if(a.x<b.x) return true;
	if(a.x>b.x) return false;
	return a.y1<b.y1;
}
SEGMENT segs[SIZEN];
int N;//线段数量
int cover[SIZEN*2]={0};
set<int> c[SIZEN];
int degree[SIZEN]={0};
int maxy=0;//最大的y坐标
bool connect(int a,int b){
	return c[a].count(b)>0;
}
class POINT{
public:
	int x,d;//点和度数
};
bool operator < (POINT a,POINT b){
	if(a.d==b.d) return a.x<b.x;
	return a.d<b.d;
}
set<POINT> data;
void addedge(int a,int b){
	c[a].insert(b);
	c[b].insert(a);
	degree[a]++;
	degree[b]++;
}
void eraseedge(int a,int b){
	c[a].erase(c[a].find(b));
	c[b].erase(c[b].find(a));
	data.erase(data.find((POINT){a,degree[a]}));
	data.erase(data.find((POINT){b,degree[b]}));
	degree[a]--;
	degree[b]--;
	data.insert((POINT){a,degree[a]});
	data.insert((POINT){b,degree[b]});
}
void work(void){
	int ans=0,x;
	vector<int> nowc;
	set<int>::iterator ckey;
	set<POINT>::iterator dkey;
	for(int i=1;i<=N;i++){
		nowc.clear();
		dkey=data.begin();
		x=dkey->x;
		for(ckey=c[x].begin();ckey!=c[x].end();ckey++) nowc.push_back(*ckey);
		for(int j=0;j<nowc.size();j++){
			for(int k=j+1;k<nowc.size();k++){
				if(connect(nowc[j],nowc[k])) ans++;
			}
		}
		for(int j=0;j<nowc.size();j++) eraseedge(x,nowc[j]);
		data.erase(data.begin());//这个点的边数变成0了
	}
	printf("%d\n",ans);
}
void addseg(int root,int x,int y,int t){
	pushdown(root);
	NODE &now=tree[root];
	if(now.left>y||now.right<x) return;
	if(now.left>=x&&now.right<=y&&now.cover!=-1){
		if(now.cover>0) addedge(now.cover,t);
		now.cover=t;
	}
	else{//叶子节点不会进入这一步
		addseg(now.lc,x,y,t);
		addseg(now.rc,x,y,t);
		update(root);
	}
}
void makegraph(void){
	build(0,maxy*2);
	for(int i=1;i<=N;i++) addseg(0,segs[i].y1*2,segs[i].y2*2,i);
	for(int i=1;i<=N;i++) data.insert((POINT){i,degree[i]});
}
void read(void){
	tot=0;
	memset(segs,0,sizeof(segs));
	memset(cover,0,sizeof(cover));
	memset(degree,0,sizeof(degree));
	data.clear();
	scanf("%d",&N);
	for(int i=1;i<=N;i++) c[i].clear();
	for(int i=1;i<=N;i++){
		scanf("%d%d%d",&segs[i].y1,&segs[i].y2,&segs[i].x);
		if(segs[i].y1>segs[i].y2) swap(segs[i].y1,segs[i].y2);
		maxy=max(maxy,segs[i].y2);
	}
	sort(segs+1,segs+1+N);
}
int main(){
	freopen("visiblesegments.in","r",stdin);
	freopen("visiblesegments.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--){
		read();
		makegraph();
		work();
	}
	return 0;
}