#include <stdio.h>
#include <stdlib.h>

typedef struct tNode{
	int left;
	int right;
	struct tNode* l;
	struct tNode* r;
	int count;
}Node;

int N;
int level[15000];
Node* root;
int result;

/*
递归创建线段树
*/
Node* create_node(int left,int right){
	Node* n=(Node*)malloc(sizeof(Node));
	n->left=left;
	n->right=right;
	n->count=0;
	n->l=NULL;
	n->r=NULL;
	if(left!=right){
		int mid=(left+right)/2;
		n->l=create_node(left,mid);
		n->r=create_node(mid+1,right);
	}
	return n;
}

/*
根据x坐标更新线段树的count值
*/
void insert(Node* node,int value){
	if(!node){
		return;
	}
	node->count++;
	int mid=(node->left+node->right)/2;
	if(value<=mid){//走左子还是右子
		insert(node->l,value);
	}else{
		insert(node->r,value);
	}
}

/*
统计[tleft,tright]的count值
*/
void search(Node* node,int tleft,int tright){
	int left=node->left;
	int right=node->right;
	if(tright<left||tleft>right){//与node区间无交集
		return;
	}
	if(tleft<=left&&tright>=right){//完全囊括node区间，无须再走孩子
		result+=node->count;
		return;
	}
	//部分交集，继续去孩子探索
	search(node->l,tleft,tright);
	search(node->r,tleft,tright);
}

int main(void){
	root=create_node(0,32000);
	int x,y;
	int i;
	scanf("%d",&N);
	for(i=0;i<N;i++){
		scanf("%d %d",&x,&y);
		result=0;
		search(root,0,x);
		level[result]++;
		insert(root,x);
	}
	for(i=0;i<N;i++){
		printf("%d\n",level[i]);
	}
	return 0;
}
目测效率应该可以了呀，自己造的15000行的数据也是秒出，感觉不该超时啊.........

• 改成数组实现就过了.......指针和数组效率差这么多吗...... (0) kensou97 2013-06-05 19:44:23