poj 2481

题意：FJ有n头牛(编号为1~n)，每一头牛都有一个测验值[S, E]，如果对于牛i和牛j来说，它们的测验值满足下面的条件则证明牛i比牛j强壮：Si <= Sj and Ej <= Ei and Ei - Si > Ej - Sj。现在已知每一头牛的测验值，要求输出每头牛有几头牛比其强壮。

 

思路：树状数组。需要对牛i比牛j强壮的条件进行理解。把牛群按照测验值E的降序排序，(E相等按S的升序)，那么接着就只需考虑S值，如果当前牛的测验值为[s, e]，那么比它强壮的牛的个数，就等于排序在它前面的，S值在[0,s]区间的牛数量(E相等的话为[0,s-1])。下面的就是树状数组部分了。此外还要考虑，如果存在两头牛区间一致的情况，只需要在求和的基础上减去就行了。总体而言这道题目和star的那个题目完全类型一致。

 

代码如下：

 

#include <iostream>
#include <algorithm>
using namespace std;
const int Max=100005;

struct  data
{
	int id,s,e;
}pre,cow[Max];

int n,ar[Max],maxval;

int lowbit(int i)
{
	return i&(-i);
}

int max(int a,int b)
{
	return a>b?a:b;
}

bool cmp(data a,data b)
{
	if(a.e==b.e)
		return a.s<b.s;
	else
		return a.e>b.e;
}


void add(int i)
{
	while (i<=maxval)
	{
		ar[i]+=1;
		i+=lowbit(i);
	}
}

int sum(int i)
{
	int ans=0;
	while (i>0)
	{
		ans+=ar[i];
		i-=lowbit(i);
	}
	return ans;
}

int main()
{
	int i,s,e,ans[Max];
	while (scanf("%d",&n)&&n)
	{
		memset(ar,0,sizeof(ar));
		maxval=0;
		for (i=0;i<n;i++)
		{
			scanf("%d%d",&s,&e);
			s++,e++;//加一的目的是为了避免0的出现
			cow[i].s=s;
			cow[i].e=e;
			cow[i].id=i;
			maxval=max(maxval,cow[i].s);
		}
		sort(cow,cow+n,cmp);
		int cnt=0;
		pre.s=pre.e=-1;
		for (i=0;i<n;i++)
		{
			if (cow[i].s==pre.s&&cow[i].e==pre.e)//如果两个牛的区间相同的处理
				cnt++;
			else
			{
				cnt=0;
				pre.s=cow[i].s;
				pre.e=cow[i].e;
			}
			ans[cow[i].id]=sum(cow[i].s)-cnt;
			add(cow[i].s);
		}
		for (i=0;i<n;i++)
			printf("%d ",ans[i]);
		printf("\n");
	}
	return 0;
}