POJ 2481 Cows 线段树

//POJ 2481 Cows 线段树
/*
题意：给n条线段（S,E），问每条线段中包含几条线段
	  线段i包含线段j的定义是Si <= Sj and Ej <= Ei and Ei - Si > Ej - Sj

思路：
将线段转化为点，这样问题就转化为问某点的左上方有多少个点
就和POJ 2352 Stars相似了
由于问的是左上方，所以点的排序应先按照y从大到小，再按x从小到大排
照样按x轴建树，同样要注意这里的x从0开始，要处理下

一个要注意的是这里的线段有可能是相同的，也就是说有重点，
这样线段树查询的时候会把那点算进去，而同样的点不满足包含的第二个定义Ei - Si > Ej - Sj
所以要特殊处理这样的数据。
PS：如果数据太大要离散化处理，这里10W还可以接受，加了个离散化之后时间反而更多了..

数据：
input：
4
1 3
1 3
1 4
1 4
output：
2 2 0 0
								
*/

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

#define N 100005
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r

int n;
int sum[N<<2],ans[N];

struct node{
	int x;
	int y;
	int id;
}s[N];

int cmp(const void *a,const void *b){
	if((*(node *)b).y != (*(node *)a).y)
		return (*(node *)b).y - (*(node *)a).y;
	return (*(node *)a).x - (*(node *)b).x ;
}

void Pushup(int rt){
	sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}

void Update(int rt,int l,int r,int x){
	if(l == r){
		++sum[rt];
		return ;
	}
	int mid = (l + r) >> 1;
	if(x <= mid) Update(lson,x);
	else		 Update(rson,x);
	Pushup(rt);
}

int Query(int rt, int l, int r, int L, int R){
	if(L <= l && R >=  r){
		return sum[rt];
	}
	int mid = (l + r) >> 1;
	int res = 0;
	if(L <= mid) res += Query(lson,L,R);
	if(R >  mid) res += Query(rson,L,R);
	return res;
}

int main(){
	int i,j;
	while(scanf("%d",&n),n){
		for(i = 0; i < n; ++i){
			scanf("%d %d",&s[i].x,&s[i].y);
			++s[i].x;
			s[i].id = i;
		}
		qsort(s,n,sizeof(s[0]),cmp);
		memset(sum,0,sizeof(sum));
		for(i = 0; i < n; ++i){
			int x = s[i].x;
			if(i && s[i].x == s[i-1].x && s[i].y == s[i-1].y)
				ans[s[i].id] = ans[s[i-1].id];
			else
				ans[s[i].id] = Query(1,1,100001,1,x);
			Update(1,1,100001,x);
		}
		for(i = 0; i < n; ++i)
			printf("%d%c",ans[i],i==n-1?'\n':' ');
	}
	return 0;
}