#include <stdio.h>
#include <iostream>
#include <memory.h>
#include <algorithm>
using namespace std;
const int maxnum=100005;
struct node
{
    int l,r;
    int pos;
}array[maxnum];
int tree[maxnum];
int ans[maxnum];
int n;

bool cmp(struct node a,struct node b)
{
    if(a.r==b.r)
        return a.l<b.l;
    return a.r>b.r;
}

void update(int index,int add)
{
    while(index<=maxnum)
     {
        tree[index]+=add;
        index+=(-index)&index;
    }
}

int getsum(int index)
{
    int sum=0;
    while(index>0)
    {
        sum+=tree[index];
        index-=(-index)&index;
    }
    return sum;
}

int main()
{
    int i;
    while(scanf("%d",&n) && n!=0)
    {
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&array[i].l,&array[i].r);
            array[i].pos=i;
        }
        sort(array,array+n,cmp);
        memset(tree,0,sizeof(tree));
        int cnt=0;
        for(i=0;i<n;i++)
        {
            if(i!=0 && array[i].l==array[i-1].l && array[i].r==array[i-1].r)
            {
                ans[array[i].pos]=ans[array[i-1].pos]; 
                cnt++;
            }
            else
            {
                update(array[i].l+1,1);//????????????????
                ans[array[i].pos]=getsum(array[i].l+1)-1+cnt;//???????????
            }
        }
        for(i=0;i<n-1;i++)
            printf("%d ",ans[i]);
        printf("%d\n",ans[i]);
    }
    return 0;
}
打问号的地方的意思是，我只对不相同的坐标点进行update，如果相同的话，cnt++,然后在求和的时候把cnt加上。测试的几个用例都能通过，但是WA,真心求助大牛啊..

• Re: 经过一段相同的区间后，cnt值要清零吧 (0) xieofyu 2012-08-27 10:51:12