poj_2481,Cows,树状数组

将e按从大到小排序，统计前i-1个中比

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

struct Item

{

    int s;

    int e;

    int x;

};

int n;

Item item[500010];

int a[500010],b[500010];

int lowbit(int x)

{

    return x&(-x);

}

int sum(int x)

{

    int ret=0;

    while(x>0)

    {

        ret=ret+a[x];

        x-=lowbit(x);

    }

    return ret;

}

void add(int x,int d)

{

    while(x<500001)

    {

        a[x]+=d;

        x+=lowbit(x);

    }

}

bool cmp(Item a,Item b)

{

    return a.e>b.e||((a.e==b.e)&&(a.s<b.s));

}

int main()

{

    while(scanf("%d",&n)&&n)

    {

        memset(a,0,sizeof(a));

        for(int i=0;i<n;i++)

            {

                scanf("%d%d",&item[i].s,&item[i].e);

                item[i].s++,item[i].e++;

                item[i].x=i;

            }

        sort(item,item+n,cmp);

        b[item[0].x]=sum(item[0].s);

            add(item[0].s,1);

        for(int i=1;i<n;i++)

        {

            if(item[i].e==item[i-1].e&&item[i].s==item[i-1].s)

            {

                b[item[i].x]=b[item[i-1].x];

                add(item[i].s,1);

            }

            else{

                b[item[i].x]=sum(item[i].s);

                add(item[i].s,1);

            }

        }

        for(int i=0;i<n;i++)

            cout<<b[i]<<" ";

        cout<<endl;

    }

    return 0;

}

e小的个数，注意相等的情况

巴特西

poj_2481,Cows,树状数组

最新文章

热门文章