Hướng dẫn cho TLEOJ Cup 2024 - Ngày 2 - Hệ thống dữ liệu

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: Sunlight

Tóm tắt đề: Cho một dãy $A$ và 3 loại thao tác:

Loại 1: thay đổi (update) giá trị của một phần tử bất kỳ.
Loại 2: tính tổng (get) $A_L + A_{L + D} + A_{L + 2D} + ... + A_{L + PD}$ .
Loại 3: khôi phục (rollback) dãy về trạng thái trước thao tác bất kỳ.

In ra kết quả của các truy vấn loại 2.

Lời giải

Đây là một bài toán kết hợp nhiều kỹ thuật xử lý truy vấn. Tùy vào việc kết hợp các kỹ thuật xử lý, ta sẽ có lời giải cho các subtask khác nhau.

Kỹ thuật 1: "Cấu trúc dữ liệu" chia căn

Ta chia một dãy độ dài $N$ thành các nhóm phần tử liên tiếp, mỗi nhóm gồm $\sqrt{N}$ phần tử. Ở mỗi nhóm, ta lưu thêm tổng các phần tử trong nhóm đó. Khi thực hiện một truy vấn yêu cầu tính tổng các phần tử liên tiếp $(L, R)$ , ta sẽ duyệt qua tất cả các nhóm nguyên vẹn trong đoạn, sau đó cộng thêm các phần tử bị thừa ra ở hai đầu.
"Cấu trúc dữ liệu" này có độ phức tạp mỗi truy vấn thay đổi (update) là $O(1)$ , trong khi độ phức tạp của mỗi truy vấn lấy tổng (get) là $O(\sqrt{N})$ .

Kỹ thuật 2: "Trải" dãy

Gọi $B_i = (A_1, A_{1 + i}, A_{1 + 2i}, ..., A_{1 + ki}, A_2, A_{2 + i}, ..., A_{i - 1}, A_{2i - 1}, ..., A_{mi - 1})$ . Với cách "trải" dãy như thế này, những phần tử có vị trí có cùng số dư khi chia cho $i$ sẽ đứng liên tiếp nhau trong dãy $B_i$ . Từ đó, truy vấn loại 2 với $D > 1$ có thể được biến thành một truy vấn tính tổng các số đứng liên tiếp.

Kỹ thuật 3: Chia hai cách làm

Xét $B$ là một hằng số. Nếu ở một truy vấn loại 2, $D \le C$ , ta sẽ xử lý truy vấn đó bằng giải thuật ngây thơ. Nếu $D < C$ , ta có thể lập các mảng $B_i$ như ở kỹ thuật 2 để xử lý trước các trường hợp khác nhau của $D$ trước khi tính toán.
Bằng cách chọn $C = \sqrt{N}$ , ta thấy rằng ta sẽ lập không quá $\sqrt{N}$ mảng $B_i$ và số phần tử được duyệt qua trong trường hợp $D \le C$ cũng không vượt quá $\sqrt{N}$ . Điều này tương ứng với không quá $\sqrt{N}$ truy vấn update mỗi lần thay đổi giá trị và một độ phức tạp không vượt quá $O(\sqrt{N})$ ở mỗi truy vấn lấy tổng (get).

Kỹ thuật 4: Cây trạng thái

Ta có thể tạo một cây với các đỉnh là các trạng thái của dãy $A$ và các cạnh là các truy vấn thay đổi (update). Với mỗi truy vấn khôi phục (rollback), ta tìm vị trí trạng thái cần khôi phục và "nối" một nhánh cây mới vào trạng thái đó.
Sử dụng kỹ thuật tìm kiếm theo chiều sâu (DFS) để đi dọc theo cây và xử lý offline các truy vấn loại 2.

Sử dụng kỹ thuật trong các subtask

Subtask 1 + 2 không sử dụng các kỹ thuật nêu trên.
Subtask 3 sử dụng kỹ thuật tổng tiền tố, subtask 4 sử dụng kỹ thuật 1.
Subtask 5 sử dụng kỹ thuật 2 và 3.
Subtask 6 sử dụng kỹ thuật 4.
Subtask 7 sử dụng kỹ thuật 1 và 4.
Subtask 8 sử dụng kỹ thuật 1, 2 và 3.
Subtask 9 sử dụng cả 4 kỹ thuật.

Bình luận

Không có bình luận nào.