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

Download