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;
}