Processing math: 100%
Solutions of Mushroom harvesting - MarisaOJ: Marisa Online Judge

Solutions of Mushroom harvesting

Select solution language

Write solution here.


User Avatar menkh    Created at    7 likes

Ta sẽ dùng Euler Tour để trải phẳng cây ra. Gọi t[] là mảng biểu diễn đường đi Euler của cây.

Gọi in[u]out[u] lần lượt là vị trí đầu tiên và vị trí cuối cùng nhất trong t của đỉnh u.

Trong t, mọi đỉnh thuộc cây con gốc u đều nằm liên tiếp từ vị trí in[u] đến out[u]. Đồng thời đỉnh v thuộc cây con gốc u khi và chỉ khi in[u]in[v]out[v]out[u].

Vậy khi đã hái nấm ở đỉnh u, ta chỉ việc đánh dấu lại đoạn [in[u],out[u]], và ở ngày i, nếu muốn biết có bao nhiêu đỉnh đã tới để hái nấm ở các ngày trước, ta chỉ việc tính tổng đoạn [1,in[ai]], tương ứng với việc đếm các đỉnh đã đánh dấu trên đường đi từ 1 tới đỉnh ai

Các thao tác trên có thể được thực hiện bằng Segment Tree + Lazy update hoặc đơn giản hơn là dùng Fenwick Tree (BIT).