poj_2352树状数组

因为y已经排好序了，用x坐标建立一维树状数组

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n;

int a[32001];

int lev[15001];

int lowbit(int x)

{

    return x&(-x);

}

int sum(int x)

{

    int ret=0;

    while(x>0)

    {

        ret+=a[x];

        x-=lowbit(x);

    }

    return ret;

}

void add(int x,int d)

{

    while(x<=32001)

    {

        a[x]+=d;

        if(x!=0)

        x+=lowbit(x);

        else break;

    }

}

int main()

{

    while(scanf("%d",&n)!=EOF){

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

    memset(lev,0,sizeof(lev));

    int b,c;

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

    {

        scanf("%d%d",&b,&c);

        //add(b,1);

        b++;

        lev[sum(b)]++;

        add(b,1);

    }

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

        printf("%d\n",lev[i]);

    }

    return 0;

}

巴特西

poj_2352树状数组

最新文章

热门文章