hdu 1541 Stars（树状数组）

题意：求坐标0到x间的点的个数

思路：树状数组，主要是转化，根据题意的输入顺序，保证了等级的升序，可以直接求出和即当前等级的点的个数，然后在把这个点加入即可。

注意：树状数组下标从1开始（下标为0的话会出错），所以把所有的x加1存储。

#include

#include

#include

using namespace std;

#define MAXN 32005

#define MAXL 15005

int c[MAXN];

int lev[MAXL];

int lowbit(int i){

return i&-i;

}

void update(int i,int val){//更新函数

while(i<=MAXN){

c[i]+=val;

i+=lowbit(i);

}

}

int sum(int i){//求和函数

int sum=0;

while(i>0){

sum+=c[i];

i-=lowbit(i);

}

return sum;

}

int main(){

int n,x,y,i;

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

memset(c,0,sizeof(c));

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

for(i=0;i

scanf("%d%d",&x,&y);

++x;//树状数组从1开始，为0的话会出错

++lev[sum(x)];//先求和

update(x,1);//后加1

}

for(i=0;i

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

}

return 0;

}

View Code

参考链接