P8969 Dream with Dynamic

简要题意

给定一个序列，区间加，区间 popcount，单点求值。

题解

对于一个操作序列 \(A\)，如果 \(A\) 包含了至少一次 popcount 操作，记该次操作及以前的操作为 \(U\)，以后的操作为 \(V\)。

注意到 \(U\) 操作后仅有 \([1,\operatorname{popcnt}(V)]\) 共 \(O(\log V)\) 种不同的结果，故我们可以把 \(V\) 的有效部分记为映射 \(V':[1,\operatorname{popcnt}(V)]\mapsto \mathbb{Z}\)。

对于 \(U\)，其为一系列加法操作复合一个 popcount 操作，记录加法操作的总和即可。

对于两个操作序列 \(u,v\) 及其复合 \(u\circ v\)，显然可以 \(O(\log V)\) 进行复合且结果仍可以使用以上方法记录。线段树维护即可，复杂度 \(O(n\log n\log V)\)。

record

2023 福建省队集训 Dream

简要题意

对于一个序列，维护：

区间加减一。
区间打标记，若有多个标记保留最小的。
区间回溯到标记，若不存在标记或 标记大于当前值 则忽略。

单点查询。

题解

想到可以用线段树维护之后的推导是平凡的，只是稍微有一些繁琐。

（下面记的东西价值不大，以后遇到这种题能想到线段树维护就肯定能够做出来了）

若有回溯操作，一个操作序列仅需要保留信息 \((minL,set,minR,tag,now)\)：
\(minL,minR\) 表示回溯前后的最小值。\(set\) 表示回溯到的值，\(tag\) 当前拥有的标记，\(now\) 表示当前的值。注意 \(minL,set\) 是相对于操作序列开始的增量，\(minR,tag,now\) 是相对于回溯到的值的增量。

若没有回溯操作则不记录 \(minL,set\) 即可。