P8969

· · 题解

刚才被人喷

所以写详细一些。

令值域为 V，考虑一个数经过一次 popcount 操作后值域只剩 \log V，于是可以考虑把相邻两次 popcount 之间的操作缩起来 .

也就是线段树标记上维护一个 \log V 长的置换 f，以及参数 A,B,p，表示原来的 x 变成了

x'=\begin{cases}x+B&p=0\\f(\operatorname{popcount}(x+A))+B&p=1\end{cases}

考虑询问的形式是单点查询于是就只需要标记可以复合运算（也就是只需要下传） .

区间加直接改 B，区间 popcount 只需遍历置换 f 求出值并更新即可，需要把 B 的贡献给 A .

于是总时间复杂度为 \Theta((n+q)\log n\log nV) .

Bonus：区间求和同时间复杂度做法？