poj2481——Cows

题意：给定区间[a,b]，问这个区间被完全覆盖多少次。注意：如果有另一区间也是[a,b]，他们不互相覆盖。

思路：树状数组，E从小到大排序，如果E相等，则S从大到小排序。从后往前遍历，这样保证先遍历的一定不被后面的覆盖。

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
class node
{
public:
	int s,e;
	int id;
};
#define maxn 100002
node p[maxn];
int c[maxn],out[maxn];
bool cmp(node &a,node &b)
{
	if(a.e <b.e )return true;
	if(a.e ==b.e &&a.s >b.s )return true;
	return false;
}
int lowbit(int x)
{
	return x&(x^(x-1));
}
int getsum(int t)
{
	int sum=0;
	while(t>0)
	{
		sum+=c[t];
		t-=lowbit(t);
	}
	return sum;
}
void Modify(int t)
{
	while(t<maxn)
	{
		c[t]++;
		t+=lowbit(t);
	}
}
int main()
{
	int n;
	while(scanf("%d",&n)&&n)
	{
		int i;
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&p[i].s ,&p[i].e );
			p[i].s ++;p[i].e ++;
			p[i].id =i;
		}
		sort(p,p+n,cmp);
		memset(c,0,sizeof(c));
		memset(out,0,sizeof(out));
		for(i=n-1;i>=0;i--)
		{
			if(i!=n-1&&p[i].s ==p[i+1].s &&p[i].e ==p[i+1].e )
			{
				out[p[i].id] =out[p[i+1].id ];
			}
			else 
			{
				out[p[i].id ]= getsum(p[i].s );
			}
			Modify(p[i].s );
		}
		for(i=0;i<n;i++)
			printf("%d ",out[i]);
		printf("\n");
	}
	return 0;
}