Codeforces Round #757 (Div. 2)
Codeforces Round #757 (Div. 2)
D2 - Divan and Kostomuksha
设计一维状态记录\(\gcd\)即可。不整除的数将自动排在后面。
\[ dp_n=\max_{p\ is\ prime} \{dp_{pn} +\#[a_i|n]-\#[a_i|pn]\} \]
time: \(O(n\log\log n)\)
E - Divan and a Cottage
线段树动态开点维护函数值。
因为题目中函数单增，故可以使用定位区间的方式确定要修改的区间。
time: \(O(n\log n)\)
space: \(O(n\log n)\)