hdu 1541 Stars（树状数组）

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

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

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

#include<iostream>
#include<stdio.h>
#include<string.h>
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<n;++i){
            scanf("%d%d",&x,&y);
            ++x;//树状数组从1开始，为0的话会出错
            ++lev[sum(x)];//先求和
            update(x,1);//后加1
        }
        for(i=0;i<n;++i)
            printf("%d
",lev[i]);
    }
    return 0;
}

View Code

hdu 1541 Stars（树状数组）

相关推荐