Problem F · Monkey and Apple-trees

§1 Đề bài tóm tắt

Có dãy cây táo đánh số $1$ đến $N \le 10^9$, ban đầu tất cả đều xanh. Có $M \le 10^5$ event:

  • Type 2 (cập nhật): đoạn $[x+c, y+c]$ chuyển toàn bộ thành chín đỏ.
  • Type 1 (truy vấn): đếm số cây đã chín đỏ trong $[x+c, y+c]$, in ra, và cập nhật $c$ bằng kết quả.

Trick: $c$ phụ thuộc kết quả query trước nên bài này online — không thể nén tọa độ trước.

§2 Quan sát chìa khóa

Range $10^9$ quá lớn để dựng segment tree thường ($\sim 4 \cdot 10^9$ node). Nhưng số query chỉ $\le 10^5$, và mỗi query chạm $O(\log N) \approx 30$ node. Tổng số node thực sự chạm khoảng $3 \cdot 10^6$ — vừa bộ nhớ. Giải pháp:

  • Sparse segment tree: chỉ allocate node khi range_set hoặc range_sum thực sự đi qua.
  • Lazy propagation: range_set không đi xuống đến tận lá — gặp 1 node bị phủ kín thì treo "lazy tag" rồi dừng. Lần sau có ai đi xuống mới push tag xuống children.
Cho người mới

§3 Tiếp cận ngây thơ

Naive 1: mảng bool ripe[10⁹] — 1 GB, MLE ngay.

Naive 2: nén tọa độ — gom tất cả $x, y$ rồi map về $\le 2M$ giá trị, dựng segtree thường. Sai: bài online, $c$ thay đổi sau mỗi query → không biết trước các giá trị cần nén.

Naive 3: segtree thường size $10^9$ — vẫn MLE vì cần $4 \cdot 10^9$ node ngay từ build.

Cả ba thất bại vì chúng cấp phát toàn bộ cây từ đầu. Quan sát: bài chỉ chạm tới rất ít node trong $10^9$ — phải tạo node lười.

Cho người mới

§4 Ý tưởng thuật toán

Hai ý tưởng kết hợp.

Ý 1 — Sparse (cây thưa). Thay vì dựng cây đầy đủ trước, ta bắt đầu chỉ với root đại diện $[0, N-1]$. Mỗi lần thuật toán cần đi xuống con trái/phải, kiểm tra: nếu con đó chưa tồn tại, tạo mới. Sau $M$ query, số node được tạo $\le M \cdot \log N$ — vừa bộ nhớ.

Ý 2 — Lazy propagation (treo nhãn lười). Khi cập nhật $[\ell, r]$ và gặp 1 node có range $[a, b]$ nằm trọn trong $[\ell, r]$, ta không đi xuống các con của nó. Thay vào đó:

  • Cập nhật freq của node = $b - a + 1$ (toàn bộ chín đỏ).
  • Treo lazy = 1 trên node — nghĩa là "cả subtree này đã được set đỏ, nhưng tao chưa thông báo cho con cháu".

Lần sau, nếu có truy vấn cần đi xuống qua node này (vì query không phủ kín), ta mới push_down: truyền lazy xuống cả 2 con (set freq + lazy của con), rồi xóa lazy ở mình. Việc trì hoãn này biến range update từ $O(N)$ thành $O(\log N)$.

Kết hợp 2 ý: range_set không tạo nodes vô ích (treo lazy là đủ); chỉ khi range_sum cần descend qua 1 node lazy, các con của nó mới được tạo.

Cho người mới

§5 Hình dung — Lazy propagation chạy thật

Widget bên dưới mô phỏng segtree trên range $[0, 7]$. Theo dõi: node nào được tạo, lazy tag ở đâu, và khoảnh khắc push_down ở step 8 — đó chính là lúc lazy được truyền xuống và 2 children mới sinh ra.

Cho người mới

§6 Vì sao lazy đúng

Bất biến lazy: tại mọi thời điểm, với mỗi node $v$, giá trị v.freq luôn phản ánh đúng tổng số cây chín trong range của $v$ — kể cả khi v.lazy = 1 chưa được đẩy xuống. Lazy chỉ là "nợ kỹ thuật" đối với các con, không ảnh hưởng giá trị tại $v$.

Khi range_set treo lazy ở $v$, ta cập nhật ngay v.freq = full coverage → bất biến giữ. Khi push_down, ta truyền lazy xuống 2 con (cập nhật freq + lazy của con) rồi reset $v$.lazy = 0. Cả 2 con bây giờ "trả nợ" được — bất biến vẫn giữ trên cả 3.

Vì range_set chỉ treo lazy ở các node phủ kín và recurse qua các node biên, mỗi update chạm $O(\log N)$ node — đó là lý do range update thành $O(\log N)$.

§7 Cài đặt

  1. Node struct. freq (sum của subtree), lazy (tag chờ push), left, right (con trỏ hoặc index, mặc định null).
  2. apply(node, len, val): cập nhật node.freq = len * val và node.lazy = val. Đây là nơi "treo" lazy.
  3. push_down(cur, l, r): tạo 2 con nếu chưa có, gọi apply trên cả 2 con với len tương ứng, reset cur.lazy = 0.
  4. range_set(cur, l, r, ql, qr, val): 3 case — disjoint return, contained → apply, partial → push_down + recurse + recompute cur.freq.
  5. range_sum(cur, l, r, ql, qr): tương tự, contained → return cur.freq; partial → push_down + recurse + sum.
  6. Online query c: đọc x, y rồi cộng $c$ vào trong main, không phải sửa input. Sau mỗi type-1, gán c = kết quả.

§8 Code C++

Block 1 — Node + apply + push_down. Đây là nơi "lazy" được treo và truyền xuống.

struct Node {
    int freq = 0, lazy = 0;
    Node *left = nullptr, *right = nullptr;
};
Node *root = new Node();

void apply(Node *cur, int len, int val) {
    if (val == 1) {              // chỉ set thành đỏ
        cur->lazy = val;
        cur->freq = len * val;
    }
}

void push_down(Node *cur, int l, int r) {
    if (!cur->left)  cur->left  = new Node();
    if (!cur->right) cur->right = new Node();
    int m = (l + r) / 2;
    apply(cur->left,  m - l + 1, cur->lazy);
    apply(cur->right, r - m,     cur->lazy);
    // Lưu ý: bài này không cần reset lazy về 0
    // vì chỉ có 1 loại update (set 1) — đã set rồi thì không undo.
}

Block 2 — range_set với 3 case (disjoint / contained / partial).

void range_set(Node *cur, int l, int r, int ql, int qr, int val) {
    if (qr < l || ql > r) return;                    // disjoint
    if (ql <= l && r <= qr) {                          // contained
        apply(cur, r - l + 1, val);                    // treo lazy, dừng
        return;
    }
    push_down(cur, l, r);                              // partial → đi xuống
    int m = (l + r) / 2;
    range_set(cur->left,  l,     m, ql, qr, val);
    range_set(cur->right, m + 1, r, ql, qr, val);
    cur->freq = cur->left->freq + cur->right->freq;    // recompute
}

Block 3 — range_sum + main. Online c được cộng vào ngay trong main.

int range_sum(Node *cur, int l, int r, int ql, int qr) {
    if (qr < l || ql > r) return 0;
    if (ql <= l && r <= qr) return cur->freq;
    push_down(cur, l, r);
    int m = (l + r) / 2;
    return range_sum(cur->left, l, m, ql, qr)
         + range_sum(cur->right, m + 1, r, ql, qr);
}

int main() {
    int M; cin >> M;
    const int N = 1e9;
    int c = 0;
    while (M--) {
        int d, x, y; cin >> d >> x >> y;
        x += c; y += c;                   // online: cộng c vào trong main
        if (d == 1) {
            c = range_sum(root, 0, N, x, y);
            cout << c << '\n';
        } else {
            range_set(root, 0, N, x, y, 1);
        }
    }
}

§9 Độ phức tạp

Time: mỗi query chạm $O(\log N) \approx 30$ node, tổng $O(M \log N) \approx 3 \cdot 10^6$ thao tác. Space: số node tạo ra $O(M \log N) \approx 3 \cdot 10^6$ nodes ≈ 100 MB với pointer. Dùng index implementation tiết kiệm hơn (~50 MB).

§10 Bẫy thường gặp

  • Quên cộng c trong main. Bài online — phải $x + c, y + c$ tại thời điểm đọc query, không phải hardcode trong input.
  • Tạo node trong range_sum ở case disjoint. Lỗi này khiến cây phình gấp $4\times$ → MLE. Chỉ tạo node trong push_down, không phải mỗi lần descend.
  • Sai công thức len cho lazy. Left con cover $[l, m]$ → len $= m - l + 1$. Right con cover $[m+1, r]$ → len $= r - m$. Đảo nhầm sẽ ra freq sai.
  • Reserve vector không đủ trong index implementation. Vector reallocate → con trỏ nội bộ invalid. Dùng tree.reserve(2 * M * log(N)) ngay đầu.
  • Quên recompute cur.freq sau khi recurse trong range_set partial case — root.freq vẫn cũ → tất cả query sai sau đó.