poj2481_code.txt

问题：求解最强的牛 算法：树状数组+二分查找(比较复杂,处理好细节)

/* source code of submission 79012, Zhongshan University Online Judge System */
#include<stdio.h>
#define maxn 100020
#include<iostream>
#include<algorithm>
using namespace std;
int c[maxn],f[maxn],ans[maxn];
int n;
struct node
{
	int i,l,r,rr;
	int num;
//	int c,f;//,ans;
};
node g[maxn];
int lowbit(int i)
{
	return i&(-i);
}
void add(int x,int i)
{
	while (x<=maxn) {
        c[x]+=i;
        x+=lowbit(x);
    }
}
int sum(int end) 
{
    int ret=0;
    while (end>0) {
        ret+=c[end];
        end-=lowbit(end);
    }
    return ret;
}
bool cmp1(node a,node b)
{
	return (a.l<b.l)||(a.l==b.l&&a.r<b.r);
}
bool cmp2(node a,node b)
{
	return a.i<b.i;
}
int b1(int l,int r,int x)
{
//	printf("%d %d %d lrx\n",l,r,x);
	if(l==r)return l;
	if(l==r-1)
	{
		if(g[r].l==x)return r;
		else return l;
	}
	int mid=(l+r)/2;
	if(g[mid].l==x)return b1(mid,r,x);
	return b1(l,mid,x);
}
int b2(int l,int r,int x)
{
	if(l==r)return l;
	if(l==r-1)
	{
		if(g[r].r==x)return r;
		else return l;
	}
	int mid=(l+r)/2;
	if(g[mid].r==x)return b2(mid,r,x);
	return b2(l,mid,x);
}
void solve()
{
	int i,j,k;
	g[0].num=0;
	add(g[0].rr,1);
	j=b1(0,n-1,g[0].l);
	k=b2(0,j,g[0].r);
	g[0].num+=j-k;
//	printf("%d %d %d\n",j,k,g[0].num);
	for(i=1;i<n;i++)
	{
		g[i].num=sum(g[i].rr);
	//	printf("%d %d %d %d\n",g[i].num,i,g[i].l,g[i].r);
		add(g[i].rr,1);
		if(g[i].l==g[i-1].l&&g[i].r==g[i-1].r)g[i].num=g[i-1].num;
		else
		{
		j=b1(i,n-1,g[i].l);
		k=b2(i,j,g[i].r);
		g[i].num+=j-k;
//			printf("%d %d %d %d\n",i,j,k,g[i].num);
		}
	}
	return;
}
int main()
{
	int i;
//	freopen("in.txt","r",stdin);
	while(scanf("%d",&n),n)
	{
		memset(c,0,sizeof(c));
		memset(f,0,sizeof(f));
//		memset(ans,0,sizeof(ans));
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&g[i].l,&g[i].r);
			g[i].i=i;
			g[i].rr=maxn-g[i].r;
		}
		sort(g,g+n,cmp1);
		solve();
		sort(g,g+n,cmp2);
		for(i=0;i<n-1;i++)printf("%d ",g[i].num);
printf("%d\n",g[i].num);

	}
	return 0; 
}