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;}