Bài gợi ý: 3U1D
Tóm tắt: Bạn cần quản lý một dãy số có độ dài thay đổi. Có bốn loại thao tác: gán tất cả phần tử trong đoạn \([L; R]\) bằng \(X\), cộng cấp số cộng \(X, 2X, \dots\) vào đoạn \([L; R]\), chèn một số \(X\) vào vị trí \(C\), và tính tổng các phần tử trong đoạn \([L; R]\).

Xét mảng ban đầu gồm \(4\) phần tử: \([10, 20, 30, 40]\). Khi thực hiện thao tác loại \(2\) trên đoạn \([2; 4]\) với \(X = 5\), ta cộng lần lượt \(5, 10, 15\) vào các vị trí này. Mảng trở thành \([10, 25, 40, 55]\). Nếu tiếp tục chèn số \(99\) vào vị trí \(3\), dãy bị đẩy sang phải thành \([10, 25, 99, 40, 55]\).

Vì có thao tác chèn phần tử, các chỉ số trong mảng liên tục thay đổi. Mảng tĩnh hay cây phân đoạn (Segment Tree) thông thường sẽ mất \(O(N)\) cho mỗi lần chèn do phải dời chỗ các phần tử phía sau. Với \(N, Q \le 10^5\), tổng số thao tác có thể lên tới \(10^{10}\) phép tính và gây quá thời gian. Vậy ta cần cấu trúc dữ liệu nào vừa chèn được phần tử ở giữa, vừa cập nhật đoạn nhanh?

Cấu trúc phù hợp ở đây là cây tìm kiếm nhị phân ngẫu nhiên theo chỉ số ẩn (Implicit Treap). Trong cây này, mỗi nút đại diện cho một phần tử của dãy. Vị trí của một phần tử trong dãy được xác định tự động qua kích thước cây con bên trái sz(left) + 1. Nhờ đó, thao tác chèn một nút mới chỉ cần cắt cây làm đôi rồi ghép lại với hàm split(root, C - 1, L, R) và merge.

Mỗi nút trong cây cần lưu các thông tin: kích thước cây con sz, giá trị tại nút val, tổng cây con sum, và hai giá trị lười (lazy tags) đại diện cho phép gán và phép cộng cấp số cộng. Khi một cây con kích thước \(S\) nhận một cấp số cộng có số hạng đầu \(A\) và công sai \(D\), lượng tổng tăng thêm được tính qua công thức \(A \times S + D \times \frac{S \times (S - 1)}{2}\).

Khi đẩy giá trị lười xuống (push_down), con bên trái nhận cấp số cộng bắt đầu từ \(A\). Nút hiện tại nhận giá trị \(A + sz(left) \times D\). Con bên phải sẽ nhận cấp số cộng mới bắt đầu từ \(A + (sz(left) + 1) \times D\) với cùng công sai \(D\).

Checklist cài đặt:

• Hàm split(t, k, l, r): tách \(k\) phần tử đầu tiên sang cây \(l\), phần còn lại sang cây \(r\).
• Hàm push_down(u): ưu tiên gán đè trước, sau đó mới cộng dồn cấp số cộng \((A, D)\) cho hai nút con.
• Với mỗi truy vấn trên đoạn \([L; R]\): dùng split tách cây thành ba phần có độ dài \(L-1\), \(R-L+1\) và phần đuôi. Cập nhật hoặc lấy kết quả tại gốc cây ở giữa, sau đó merge cả ba phần lại theo đúng thứ tự.

Bài tập tương tự:

• CSES - Cut and Paste | Cắt và dán: Luyện thao tác cắt và ghép cây con bằng Treap chỉ số ẩn.
• CSES - Reversals and Sums | Đảo ngược và tính tổng: Luyện kỹ thuật đẩy nhãn lười (lazy propagation) và tính tổng đoạn trên Treap.

Để bắt đầu, hãy viết hàm split và merge cơ bản, sau đó bổ sung hàm push_down để quản lý hai nhãn lazy_set và lazy_add.