#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#include "malloc.h"
int cmp(const void *a,const void *b){
	return (*(int *)a)-(*(int*)b);
}
struct {
	int l,r,c;
}st[30001];//线段树的节点
int col[10001];//颜色
int p[20001];//离散化后的值
int m;//离散化后的数目
int x[10001];//左端点
int y[10001];//右端点
int *hash;//原来的值到离散的值的映射
int cc;//结果
void build(int a,int b,int ind){
	st[ind].l=a;
	st[ind].r=b;
	st[ind].c=0;
	if(a==b)
		return;
	int mid=(a+b)/2;
	build(a,mid,ind*2);
	build(mid+1,b,ind*2+1);
}
void update(int a,int b,int ind,int k){
	if((a<=st[ind].l&&st[ind].r<=b)){
		st[ind].c=k;
		return;
	}
	if(st[ind].c>0){
		st[ind*2].c=st[ind].c;
		st[ind*2+1].c=st[ind].c;
	}

	st[ind].c=-1;
	int mid=(st[ind].l+st[ind].r)/2;
	if(a<=mid)
		update(a,b,ind*2,k);
	if(b>mid)
		update(a,b,ind*2+1,k);
}
void count(int ind){
	if(st[ind].c>0){
		if(col[st[ind].c]==0)
			cc++;
		col[st[ind].c]=1;
		return;
	}
	if(st[ind].c==0)
		return;

	count(ind*2);
	count(ind*2+1);
	return;
}

int getindex(int a){
	int from,to,mid;
	from=0;
	to=m-1;
	
	while(from<=to){
		mid=(from+to)/2;
		if(p[mid]==a)
			return mid;
		if(p[mid]<a){
			from=mid+1;
		}
		else{
			to=mid-1;
		}
		
	}
	printf("error\n");
	return -1;
}
int getindex2(int a){
	   if(hash[a]>=0&&hash[a]<m)
		return hash[a];
		printf("error");
}
void inithash(){
	int i;
	for(i=0;i<m;i++){
		hash[p[i]]=i;
	}
}
int main(){
	int c;
	int n;
	scanf("%d",&c);
	hash=(int*)malloc(sizeof(int)*20000001);
	while(c--){
		int i;
		cc=0;
		memset(col,0,sizeof(col));
		scanf("%d",&n);
		for(i=0;i<n;i++){
			scanf("%d%d",&x[i],&y[i]);
			p[2*i]=x[i];
			p[2*i+1]=y[i];
		}
		//=================离散化=========================
		qsort(p,2*n,sizeof(int),cmp);
		for(i=0,m=0;i<2*n;i++){
			if(i==0||p[i]!=p[i-1]){
				p[m++]=p[i];
			}
		}
		inithash();
		//===============用线段树处理====================
		build(1,m,1);
		for(i=0;i<n;i++){
			update(getindex(x[i])+1,getindex(y[i])+1,1,i+1);
		}
		count(1);
		printf("%d\n",cc);
	}
}

• Re:下面是挂的代码，用线段树+离散化，RUNTIme error求解～～ (25) point3251 2011-02-13 15:19:35