Editorial for DIVISORPART

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Đặt $f_{i} = 0$ nếu $a_{i - 1}$ là ước của $a_{i}$ và $f_{i} = i$ nếu $a_{i - 1}$ không phải là ước của $a_{i}$ . Suy ra. $S_{i} = {max}_{j = 1}^{i} f_{i}$

Xây dựng segment tree mà mỗi node trong cây lưu giá trị max $f_{i}$ trong đoạn node đó quản lý. Như vậy ta có thể dễ dàng tính được $S_{i}$ thông qua segment tree.

Khi thay đổi giá trị của $a_{i}$ , chỉ có $f_{i}$ và $f_{i + 1}$ là có thể thay đổi do đó ta chỉ cần cập nhật lại 2 vị trí này trong segment tree.

Độ phức tạp: $O (n \cdot l o g_{2} n)$

Comments

Please read the guidelines before commenting.

There are no comments at the moment.