做题记录 25.9.30

· · 个人记录

\purple\odot CF626G Raffles

先忽略对 l 的修改，考虑一组固定的 l_{1\sim n}

设此时 i 号中选择了 c_i，则它变为 c_i+1 的收益为

p_i\left(\frac{c_i+1}{c_i+1+l_i}-\frac{c_i}{c_i+l_i}\right)=\frac{p_il_i}{(c_i+1+l_i)(c_i+l_i)}

用堆贪心地维护这些收益，单次询问容易做到 O(t\log n)

然后考虑修改，发现对 l_i 的修改为 \pm 1，因此对具体选择的方案的修改也是 O(1) 的，用 std::multiset 维护目前选择的和没有选择的分界线的两端，容易 O(\log n) 维护每次修改

总时间复杂度 O((n+t+q)\log n)

代码

参考