Poj 2352 Stars 题解

本题是一维树状数组的典型应用

代码：

#include <stdio.h>#include <stdlib.h>#include <string.h>using namespace std;int c[32010];int level[32010];//求2的K次幂int lowbit(int t){    return t&(-t);}//更新树状数组void update(int t){    while(t<32010)    {        ++c[t];        t+=lowbit(t);    }}//获取前N项和int getSum(int t){    int sum = 0;    while(t>0)    {        sum+=c[t];        t-=lowbit(t);    }    return sum;}int main(){    int n;    int x;    int y;    int i;    int sum;    scanf("%d",&n);    memset(c,0,sizeof(c));    memset(level,0,sizeof(c));    for(i = 0;i<n;i++)    {        scanf("%d%d",&x,&y);        ++x;//星星的左边可以从0开始，但是update函数的参数却不能是0，所有向后移一位        update(x);        sum = getSum(x);        ++level[sum];    }    for(i = 0;i<n;i++)    {        printf("%d\n",level[i+1]);    }    return 0;}