【题解】P8969 Dream with Dynamic | 线段树 思维
ღꦿ࿐
·
·
题解
看到这个题的题解都很简略，所以我写详细点。
首先这个 \operatorname{popcount} 函数的势能性质是不好分析的，因为 a\geq p 时 \operatorname{popcount}(a) 不一定大于 \operatorname{popcount}(b)， 所以只能考虑 \operatorname{popcount} 的值域为 O(\log V) 的性质，
线段树维护，将操作分为若干线段，接下来如果某个段在某个时刻被求过一次 \operatorname{popcount}，后面无论再怎么整段地加，它的值都可以表示成 \operatorname{popcount}( \dots) + b 的形式，所以我们考虑在线段树上维护标记：
我们把操作序列形象地描述出来，加法是 $\texttt a$，区间做 $\operatorname{popcount}$ 是 $\texttt p$，那么操作序列例如
$$\texttt{apapppaaapaaa}$$
我们把加法合并成一次再按照 $p$ 分段：
$$\texttt{ ap| ap | ap | ap | ap | a}$$
就变成了若干次 $\operatorname{popcount}(x+b)$ 的复合，这就是一个值域 $O(\log V)$ 的函数，从第二次开始定义域也变成了 $O(\log V)$，于是我们直接维护第一步函数的样子，暴力维护第二步开始以及后面函数的复合，单独计算最后的加法就可以做到了。
纯加法需要单独记录，它的值域不同。复合时也需要特判。
时间复杂度 $O(q\log n\log V)$ ，可以跑进 4s，做一些卡常性质的处理（如对于区间长度小于 $3\log V$ 的区间，再次下传标记是不优秀的，不如暴力）即可跑进 2s，目前最优解第二。