CVJETICI - Cvjetici

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<iostream>
using namespace std;

const int N = 100000;
int bit[N];

void update(int idx, int v) {
    for(int x = idx; x < N; x |= x + 1)
        bit[x] += v;
}

void updateOne(int idx, int v) {
    bit[idx] += v;
    for(int z = idx | (idx + 1), x = idx + 1; x < N && x != z; x |= x + 1)
        bit[x] -= v;
}

int get(int idx) {
    int res = 0;
    for(int x = idx; x >= 0; x -= ~x & (x + 1))
        res += bit[x];
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    int n; cin >> n;
    for(int i = 0; i < n; ++i) {
        int l, r; cin >> l >> r; --l; --r;
        int fl = get(l), fr = get(r);
        printf("%d\n", fl + fr);
        updateOne(l, -fl); updateOne(r, -fr);
        update(l + 1, 1); update(r, -1);
    }
    return 0;
}

Download