题解：P9393 紫丁香

· · 题解

P9393 紫丁香

一道每一步都很简单但拼在一起就较为困难的题。

首先观察询问发现是查询二进制下最大值，非常套路的可以从高到低枚举每一位是否选，加上之后 check 一遍是否合法。（其它题解这里说是二分但我感觉不太一样，毕竟这里直接二分是没有单调性的（？）

先考虑对于单个询问怎么做。观察枚举出来的答案，那些为 0 的位置可以随意处理，为 1 的位置就代表这个位置在最后的若干个操作中一定是一个 1 和若干个 -。这启示我们倒着考虑操作，从答案往初始状态推导。

假设当前我们要保证集合 S 中的位置全部是 1，其他位置任意。枚举一个操作，分类讨论一个钦定为 1 的位置在经过这次还原之后的状态。

下文设这一轮选择的操作的字符串为 T，考虑的位置编号为 x。

  1. 那么在之后的还原过程中这一位是什么其实已经不重要了，可以从 $S$ 中删除 $x$。
  2. 那么这个位置一定是 ```0```，所以这种情况的 $T$ 一定不能选择。
  3. 这个操作不会对最终的这一位产生影响，所以不变化。

因此我们得到了一个较为暴力的做法，每一次暴力枚举操作，进行更改。由于这样操作到无法操作的状态是唯一的，最终合法的条件就是 S 为询问串中为 1 的位置的集合的子集。实现较优秀的话或许是 \operatorname{O}(nmq) 的。

我们考虑对上述算法进行优化。设 g_S 表示集合 S 进行任意一个操作能将那些元素从 S 中删除，h_S 表示集合 S 中的位置不为 0 的那些操作中 1 的位置的并，可以发现 g 就是 h 的高位后缀或。

于是对于一个 S，只需要每次将 g_S 从 S 中删去即可。

接着考虑多组询问。可以预处理 f_S 表示 S 能操作到的集合大小最小的集合是什么，转移直接删去 g_S 即可，时间复杂度 \operatorname{O}(nm+m\times 2^m)。