VOI 2026, Bài 5

1. Tóm tắt đề

Cho cây $N$ đỉnh đánh số từ $1$, đỉnh thứ $i$ có trọng số nguyên không âm $A_i$.

Có $Q$ truy vấn, truy vấn thứ $t (1 \leq t \leq Q)$ được mô tả bằng $3$ số nguyên dương $x_t, y_t, w_t$ với ý nghĩa là gán $A_i = A_i \% w_t$ với mọi đỉnh $i$ nằm trên đường đi từ $x_t$ đến $y_t$.

Yêu cầu: Sau mỗi truy vấn thứ $t$, in ra $(A_1 \% t) + (A_2 \% t) + \dots + (A_n \% t)$.

Giới hạn:

• $N, Q \leq 2 \times 10^5$.
• $0 \leq A_i \leq 2 \times 10^5$.

Tính điểm:

• Subtask $1 (20\%)$: $N, Q \leq 5000$.
• Subtask $2 (20\%)$: Cây là đường thẳng $1 - 2 - \dots - N$ và $A_i \leq 2$.
• Subtask $3 (20\%)$: Cây là đường thẳng $1 - 2 - \dots - N$ và $x_t = y_t$ ở mọi truy vấn.
• Subtask $4 (20\%)$: Cây là đường thẳng $1 - 2 - \dots - N$.
• Subtask $5 (20\%)$: Không có ràng buộc gì thêm.

2. Subtask 1

Duyệt trâu, độ phức tạp $O(NQ)$.

3. Subtask 2

Dễ thấy từ truy vấn thứ $3$ trở đi thì kết quả là cố định nên chỉ cần tính kết quả ở truy vấn $1, 2, 3$.

4. Subtask 3

Ta có $A_i \% t = A_i - \lfloor \frac{A_i}{t} \rfloor \times t$ nên ta chỉ cần tính tổng $\lfloor \frac{A_1}{t} \rfloor + \dots + \lfloor \frac{A_n}{t} \rfloor$. Mặc khác có tối đa $2\sqrt{A_i}$ giá trị khác nhau của $\lfloor \frac{A_i}{t} \rfloor$ nên ta có thể cập nhật lại tổng dễ dàng. Độ phức tạp là $O(N \sqrt{N})$.

5. Subtask 4

Sử dụng SegmentTree, mỗi nút quản lý min. Do mỗi lần chia lấy dư số đó giữ nguyên hoặc giảm đi ít nhất một nửa nên mỗi nút lá của SegmentTree được thăm không quá $\log(A_i)$ lần. Từ đó ở truy vấn $t$, nếu ta thấy min của nút hiện tại trên SegmentTree lớn hơn $t$ thì bỏ qua và không xét các nút con của nút đó nữa.

Sử dụng thêm FenwickTree để truy vấn $f(x)$ là tổng các số $A_i \leq x$ và $g(x)$ là số lượng số $A_i \leq x$. Nhận xét vì mỗi số thay đổi không quá $\log(A_i)$ lần nên số lần cập nhật trên FenwickTree không quá $N \log N$.

Đặt $f(l, r) = f(r) - f(l - 1)$ và $g(l, r) = g(r) - g(l - 1)$. Ở truy vấn thứ $t$ để lấy kết quả, ta lấy tổng:

$$f(0, t - 1) + f(t, 2t - 1) - t \times g(t, 2t - 1) + f(2t, 3t - 1) - 2t \times g(2t, 3t - 1) + \dots$$

6. Subtask 5

Sử dụng HLD kết hợp với Subtask 4. Độ phức tạp $O(N \log^2 N)$.