P6587 超超的序列 加强

题目描述

给定一个序列 ，每次给出 和 。每次对所有满足 的 进行操作和查询。

思路

考虑用线段树维护。但是本题的难点在于，所有的操作都不是直接对区间的操作，我们要想办法把其变成对区间的操作。

思考当前 与 和 的关系：
在二进制下， 可以看作把 的后 位留下，前面的位数直接不要了。那么如果 与 的后 位相同，则 。

所以，建树时我们可以钦定树边存在 0 和 1 的边权，那么一个叶子节点到根的链上所有边权拼在一起组成的二进制数，即为当前节点对应在原序列上的编号。

具体地：
令节点到右儿子的边权为 1，到左儿子的边权为 0。每次操作时从根节点开始，以左右儿子节点的选取，来代表当前节点对应在原序列上的位置 的值。
注意树的边权组成的二进制数代表当前位置 的值（从根节点开始到当前节点），即 的后缀。

每次操作时，对所有与 有相同 位的后缀的节点进行修改，这些节点由于后缀相同，所以处于线段树的同一个区间中。考虑标记永久化，则只用对与 有相同 位后缀的最浅节点做修改即可。
此时对序列的操作就变成了对树上一个区间的操作。代码只要模拟我们刚刚所说的过程即可。