poj - 2352 - Stars（树状数组）

题意：依次给出N个星星的坐标（y坐标以非递减的顺序输入），对于每个星星，她的等级等于她左下方的星星的个数和（包括边界上的星星），要求输出等级0到等级N-1的星星的个数。（0 <= X, Y, <= 32000, 1 <= N <= 15000）

题目链接：http://poj.org/problem?id=2352

——>>设x[i]表示横坐标为i的星星有多少颗，那么对于一个单一询问（星星(k, y)的等级是多少？），要求的是x[]的前k项和，于是树状数组来了。。。

坑点：坐标范围覆盖0，对树状数组的一般写法是从1开始计数的，所以，对于每个x坐标+1来计算。假如不+1，我这返回的结果竟是TLE。。。

#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 15000 + 10;
const int maxf = 32000 + 10;

int N, lev[maxn];
int c[maxf];

int lowerbit(int x) {
    return x & (-x);
}

int sum(int x) {
    int sum = 0;
    while(x > 0) {
        sum += c[x];
        x -= lowerbit(x);
    }
    return sum;
}

void add(int x) {
    while(x < maxf) {
        c[x]++;
        x += lowerbit(x);
    }
}

int main()
{
    int x, y;
    while(scanf("%d", &N) == 1) {
        memset(c, 0, sizeof(c));
        memset(lev, 0, sizeof(lev));
        for(int i = 0; i < N; i++) {
            scanf("%d%d", &x, &y);
            lev[sum(++x)]++;
            add(x);
        }
        for(int i = 0; i < N; i++) printf("%d\n", lev[i]);
    }
    return 0;
}

poj - 2352 - Stars（树状数组）

原文：http://blog.csdn.net/scnu_jiechao/article/details/18629421