HDU1556 Color the ball(树状数组 区间更新)

题目链接

中文题。

对于每次对[a, b]的涂色,做如下更新:add(a, 1)和add(b+1, -1)。前缀和就代表了涂色次数。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
using namespace std;
int n;
int a[100005];
int lowbit(int x){
    return x&(-x);
}
void add(int pos , int num){
    while(pos <= n){
        a[pos] += num;
        pos += lowbit(pos);
    }
}
int sum(int n){
    int sum = 0;
    while(n > 0){
        sum += a[n];
        n -= lowbit(n);
    }
    return sum;
}
int main(){
    //freopen("a.txt", "r", stdin);
    while(~scanf("%d", &n) && n){
        memset(a, 0, sizeof(a));
        for(int j = 0; j < n; j++){
            int x, y;
            scanf("%d %d", &x, &y);
            add(x, 1);
            add(y+1, -1);
        }
        for(int i = 1; i <= n; i++){
            cout << sum(i);
            if(i != n) cout << " ";
        }
        cout <<endl;
    }

    return 0;
}

Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with 树状数组