1. Nhận xét

Gọi độ dài đoạn sông của các xí nghiệp theo thứ tự thượng nguồn→hạ lưu là một dãy ~L_1, L_2, ..., L_m~ (~m~ thay đổi).

Tổng thuế tại một thời điểm: ~S = \sum_{i=1}^{m} L_i^2~.

Mỗi biến động chỉ đụng tới:

• ~1~ phần tử (tách), hoặc
• ~1~ phần tử và tối đa ~2~ hàng xóm (phá sản).

Vì vậy, ~S~ có thể cập nhật bằng vài phép cộng/trừ (O(1)) nếu truy cập/xóa/chèn theo chỉ số nhanh.

2. Cập nhật tổng thuế (không phụ thuộc cấu trúc dữ liệu)

Tách ~(e = 2)~

Đoạn ~L~ tách thành:

• ~x = \lfloor L/2 \rfloor~ (phía thượng lưu, ngắn hơn khi lẻ)
• ~y = L - x~ Cập nhật: ~S \leftarrow S - L^2 + x^2 + y^2~.

Phá sản (e = 1)

Xóa đoạn ~L~ khỏi dãy: ~S \leftarrow S - L^2~.

• Nếu chỉ có ~1~ hàng xóm có độ dài ~A~: ~A \leftarrow A+L~, ~S \leftarrow S - A^2 + (A+L)^2~.
• Nếu có ~2~ hàng xóm trái/phải ~A,B~: chia ~L~ thành ~x=\lfloor L/2\rfloor~, ~y=L-x~, ~A \leftarrow A+x~, ~B \leftarrow B+y~, ~S \leftarrow S - A^2 - B^2 + (A+x)^2 + (B+y)^2~.

Phần còn lại của bài toán là quản lý dãy động theo chỉ số.

3. Mô hình hoá thành thao tác trên dãy động

Cần hỗ trợ các phép:

• lấy phần tử thứ ~c~
• xóa phần tử thứ ~c~
• chèn ~1~ phần tử ngay sau vị trí ~c~ (khi tách)
• lấy hàng xóm trái/phải của ~c~

Tất cả phải chạy ~O(\log n)~.

Đây chính là bài toán dynamic sequence.

4. Cấu trúc dữ liệu

Dùng cây cân bằng theo thứ tự (implicit), mỗi node là một xí nghiệp, lưu:

• ~val~ = độ dài đoạn sông
• ~sz~ = số node trong cây con

Chọn Implicit Splay vì:

• có thể viết hoàn toàn iterative (không stack overflow),
• hỗ trợ tự nhiên kth, split, merge theo vị trí,
• ~O(\log n)~ amortized.

(Implicit Treap cũng được, nhưng bản iterative rất dễ dính lỗi chu trình/stack nếu cài sai.)

5. Các phép chuẩn cần có

• kth(root, k): tìm node thứ ~k~ theo inorder dựa trên ~sz~.

• split(root, k): tách thành ~(A,B)~ sao cho ~A~ chứa ~k~ phần tử đầu.

  • Splay node thứ ~k+1~ lên gốc, cắt cây con trái.

• merge(A,B): nối hai dãy (mọi phần tử A đứng trước B).

  • Splay phần tử phải nhất của ~A~ lên gốc, gắn ~B~ vào con phải.

6. Xử lý một biến động (khung thao tác)

Tách dãy thành ~A | mid | C~ bằng 2 lần split.

• Nếu tách:

  • tính ~x,y~
  • cập nhật ~S~
  • tái sử dụng node mid cho ~x~, tạo thêm ~1~ node mới cho ~y~, rồi merge lại.

• Nếu phá sản:

  • cập nhật ~S -= L^2~
  • nếu thiếu hàng xóm thì lấy ~1~ node biên của phần còn lại
  • nếu đủ hai hàng xóm thì lấy cuối A và đầu C
  • cộng thêm phần chia vào ~val~ của hàng xóm, cập nhật ~S~
  • merge lại.

7. Độ phức tạp

Mỗi query dùng hằng số lần split/merge/kth ⇒ ~O(\log(n+k))~ amortized.

Tổng thời gian: ~O((n+k)\log(n+k))~. Bộ nhớ: ~O(n+k)~ node.

8. Lưu ý cài đặt hay sai

• Chia lẻ: thượng lưu nhận phần ngắn hơn ⇒ luôn dùng ~x=\lfloor L/2\rfloor~ cho phía trái.
• Type 2: chỉ tạo 1 node mới, không tạo ~2~ node mới rồi bỏ node cũ (tránh tràn node).
• Dùng long long cho ~S~ và bình phương.