> #include<stdio.h>
> #include<string.h>
> #include<stdlib.h>
> 
> #define maxn 110001
> 
> int i,j,n,m,s[maxn],e[maxn],p[maxn],q[maxn],ans[maxn],tree[300000],left[300000],right[300000];
> int maxa;
> 
> int sorts(int a,int b){
> 	int i,j,x,y,dome;
> //	dome=rand()/RAND_MAX*(b-a)+a;
> 	dome=(a+b)/2;
> 	if (b>a) dome++;
> 	x=s[dome];i=a;j=b;
> 	do{
> 		while (s[i]<x&&i<b) i++;
> 		while (s[j]>x&&j>a) j--;
> 		if (i<=j){
> 			p[q[i]]=j;p[q[j]]=i;
> 			y=q[i];q[i]=q[j];q[j]=y;
> 			y=s[i];s[i]=s[j];s[j]=y;
> 			y=e[i];e[i]=e[j];e[j]=y;
> 			i++;j--;
> 		};
> 	}while (i<=j);
> 	if (a<j) sorts(a,j);
> 	if (i<b) sorts(i,b);
> 	return 0;
> };
> 
> int sorte(int a,int b){
> 	int i,j,x,y;
> 	x=e[(a+b)/2];i=a;j=b;
> 	do {
> 		while (e[i]>=x&&i<b) i++;
> 		while (e[j]<=x&&j>a) j--;
> 		if (i<=j){
> 			p[q[i]]=j;p[q[j]]=i;
> 			y=q[i];q[i]=q[j];q[j]=y;
> 			y=s[i];s[i]=s[j];s[j]=y;
> 			y=e[i];e[i]=e[j];e[j]=y;
> 			i++;j--;
> 		};
> 	}while (i<=j);
> 	if (a<j) sorte(a,j);
> 	if (i<b) sorte(i,b);
> 	return 0;
> };
> 
> int max(int a,int b){
> 	if (a>b) return a;else return b;
> };
> int min(int a,int b){
> 	if (a<b) return a;else return b;
> };
> 
> 
> int count(int a,int now){
> 	int dome=0,mid;
> 	if (now==0) return tree[1];
> 	while (left[a]<=right[a]){
> 		if (now==left[a]){ dome+=tree[a];break;};
> 		mid=(left[a]+right[a])/2;
> 		if (now<=mid){ dome+=tree[a*2+1];a=a*2;}
> 		else a=a*2+1;
> 	};
> 	return dome;
> };
> 	
> 
> int color(int a,int now){
> 	int mid;
> 	while (left[a]!=right[a]){
> 	tree[a]++;
> 	mid=(left[a]+right[a])/2;
> 	if (now<=mid) a=a*2;
> 	else a=a*2+1;
> 	};
> 	tree[a]++;
> 	return 0;
> };
> 
> int maketree(int a,int l,int r){
> 	left[a]=l;
> 	right[a]=r;
> 	if (l==r) return 0;
> 	maketree(a*2,l,(l+r)/2);
> 	maketree(a*2+1,(l+r)/2+1,r);
> 	return 0;
> };
> 
> 
> int main(){
> 	maketree(1,0,100000);
> //	printf("%d",maxa);
> 	scanf("%d",&n);		
> 	while (n){
> 		for (i=1;i<=n;i++){
> 			scanf("%d %d",&s[i],&e[i]);
> 			p[i]=i;q[i]=i;
> 		};
> 		sorts(1,n);
> 		i=1;
> 		while (i<n){
> 			j=i;while (s[i]==s[j]&&j<=n)j++;
> 			if (j-1>i) sorte(i,j-1);
> 			i=j;
> 		};
> 		i=1;
>         while (i<=n){
> 			ans[i]=count(1,e[i]);
> 			color(1,e[i]);
> 			j=i+1;
> 			while (j<=n&&s[i]==s[j]&&e[i]==e[j]) {ans[j]=ans[i];j++;};
> 			i=j;
> 		};
> 		for (i=1;i<n;i++) printf("%d ",ans[p[i]]);
> 		printf("%d\n",ans[p[n]]);
> scanf("%d",&n);
> if (n) memset(tree,0,sizeof(tree));		
> 	};
> 	return 0;
> };

• sorry,贴错了，再贴一次 (2296) Spacesheep 2005-07-13 18:24:16