HDU 1556 트 리 배열

전송 문: HDU 1556
해제
트 리 배열 템 플 릿 문제 구간 염색 + 통계 횟수 를 위로 조회 하고, 아래 통 계 를 통 해 a 이후 구간 에 염색 업 데 이 트 를 한 번 더 한 다음 b 이후 염색 업 데 이 트 를 한 번 줄 이면 [a, b] 데 염색 업 데 이 트 를 완성 합 니 다.
AC code:

#include
#include
#include
using namespace std;

#define lowbit(x) (x & (-x))
#define LL long long 
#define debug 1

const int maxn(100005);
const int mod(1e9 + 7);

int c[maxn];

int n;



void add(int x, int y, int v) {

    for (int i = x; i <= n; i += lowbit(i)) {
        c[i] += v;
    }

    for (int i = y + 1; i <= n; i += lowbit(i)) {
        c[i] -= v;
    }
}

int getSum(int x) {
    int res = 0;

    for (int i = x; i; i -= lowbit(i)) {
        res += c[i];
    }

    return res;
}

int main() {
#if debug
    freopen("in.txt", "r", stdin);
#endif //debug

    int a, b;

    while (cin >> n, n) {

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

        for (int i = 1; i <= n; ++i) {
            cin >> a >> b;
            add(a, b, 1);
        }

        for (int i = 1; i <= n; i++) {
            int ans = getSum(i);
            cout << ans << (i == n ? "
" : " ");
        }
    }

    return 0;
}