#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;
};

• Re:help!!!!!!!!!!! my code is here (2569) Spacesheep 2005-07-13 18:09:07
  • sorry,贴错了，再贴一次 (2296) Spacesheep 2005-07-13 18:24:16