【ULR #2】Picks loves segment tree IX

· · 个人记录

下面是口胡题解

考虑如果一段操作没有 +1 操作，容易预处理求出某一位的变化情况（0/1/rev/不变）。

如果有 +1 操作，影响效果是 bitxor 11111 ，但似乎难以知道这个操作的影响。

考虑进位一次以后，变成了 ?00000。（但上面会往上 +1 ，可能会产生新的 0）

考虑两个数组 f,g

$g(i,j)$ 表示某次 +1 后第 $j+1$ 位以下变成 10000 ，到第 $g(i,j)$ 的 +1 操作后第 $j$ 位以下变成 00000 （多一个 0） 每次询问的时候： 从当前位置跳 $g(i,j)$ ，跳到某次 +1 进位影响到询问的那一个位。 接下来变成了 x00000 ... 接下来跳 $f(i,j)$ ，每次跳一个 $f(i,j)$ 的+1操作就会把询问的那个位影响 xor 1，其他的 +1 操作是没影响的。（当然跳的中间询问的位也会改变，但是这个影响是容易查询的。） （主要思想就是考虑询问的位一定会在每个 $f(i,j)$ 的+1操作时被影响。） 可以把 $i\to f(i,j)$ 变成一颗树然后树剖优化查询。 ---