CVJETICI - Cvjetici
Tác giả: ladpro98
Ngôn ngữ: C++
#include <bits/stdc++.h>
const int lim = 100005;
using namespace std;
int MAX[4 * lim], CNT[4 * lim], lazy[4 * lim];
struct node {
int l, r, id;
void diffuse() {
if (lazy[id] == 0) return;
MAX[id] += lazy[id];
if (l != r) lazy[id << 1] = lazy[id << 1 | 1] += lazy[id];
lazy[id] = 0;
}
node (int _l, int _r, int _id) {l = _l; r = _r; id = _id; diffuse();}
node left() {return node(l, l + r >> 1, id << 1);}
node right() {return node((l + r >> 1) + 1, r, id << 1 | 1);}
void Assign(int i, int j) {
if (l > r || r < i || j < l) return;
if (i <= l && r <= j) {lazy[id]++; diffuse(); return;}
left().Assign(i, j); right().Assign(i, j);
}
void Inc(int i) {
if (l > r || r < i || i < l) return;
if (l == r) {CNT[id] = MAX[id]; return;}
left().Inc(i); right().Inc(i);
CNT[id] = CNT[id << 1] + CNT[id << 1 | 1];
}
};
int main() {
int n, l, r;
scanf("%d", &n);
node Root (1, lim, 1);
int last = 0;
for(int i = 1; i <= n; i++) {
scanf("%d %d", &l, &r);
if (l + 1 < r)
Root.Assign(l + 1, r - 1);
Root.Inc(l); Root.Inc(r);
printf("%d\n", CNT[1] - last);
last = CNT[1];
}
return 0;
}