[代码] hdu 1556 color the ball(树状数组)

- 传送门 -

　http://acm.hdu.edu.cn/showproblem.php?pid=1556
　

- 题目描述 -

　N个气球排成一排，从左到右依次编号为1,2,3....N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽"牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了，你能帮他算出每个气球被涂过几次颜色吗？
　

- 输入 -

　每个测试实例第一行为一个整数N,(N <= 100000).接下来的N行，每行包括2个整数a b(1 <= a <= b <= N)。
当N = 0，输入结束。
　

- 输出 -

　每个测试实例输出一行，包括N个整数，第I个数代表第I个气球总共被涂色的次数。
　

- 样例输入 -

3
1 1
2 2
3 3
3
1 1
1 2
1 3
0
　

- 样例输出 -

1 1 1
3 2 1
　

- 代码 -

#include<cstdio>
#include<cstring>
using namespace std;

const int M = 1e5 + 5;

int B[M];
int x, y, n, m;
int f;
char ch;

template <typename T> void read(T &x) {
    x = 0, f = 1; ch = getchar();
while (ch > '9' || ch < '0') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x*10 + ch - '0'; ch = getchar(); }
    x *= f;
}

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

void upt(int x, int v) {
while (x <= n) {
        B[x] += v;
        x += lowbit(x);
    }
}

int ask(int x) {
int ans = 0;
while(x > 0) {
        ans += B[x];
        x -= lowbit(x);
    }
return ans;
}

int main() {
while(~scanf("%d", &n)) {
if (!n) break;
        memset(B, 0, sizeof B);
for (int i = 1; i <= n; ++i) {
            read(x); read(y);
            upt(x, 1); upt(y + 1, -1);
        }
for (int i = 1; i < n; ++i)
            printf("%d ", ask(i));
        printf("%d", ask(n));
        puts("");
    }
return 0;
}