雨森润奈

· · 题解

不需要卡常的 O(\frac{nmq}{w}) 做法！

考虑容易发现与 0 和或 1 特别强而反过来则没有用，启发我们时光倒流，那么对于一个点，我们考虑他如果与 0，那么那些 0 点都是因为这次与操作才变为 0，而之前是什么我并不关心，设为任意位，反过来或 1 也是一样。

然后遇到了一个困难的问题就是如果遇到两种选择怎么搞，容易发现这样的话随便选一个，最后剩下的有用的数必然只有一种，考虑用任意位和确定位重新建立字符串，以确定位为 1 时为例。

容易发现如果我在这个位置选择或，相当于是让我的任意点集合与当前所指向的集合或在一起。

如果选择与要求我的任意点集合包含我按位取反后的集合，然后你发现按照这个思路，如果在这个位置选择或，我们必然会得到全集，后续怎么选都无所谓可以直接产生贡献。

于是我们能够确认我们每次选什么，得到了一个 O(\frac{nmq}{w}) 的做法。

我们肯定不希望得到这个复杂度考虑优化一下后面的部分，容易发现如果把每个点后面第一个与他相同的元素位置记录下来，那么每次相当于所有点都往后取一次，把所有最大值保留并在那个位置贡献答案，然后一直做，如果一直维护这个肯定做不了，考虑这样的话意味着最终选取的点集合一定能用一个点替代，而这个长得有点像字典序的东西显然可以用字符串哈希维护。

这样的话我们就把后面变成了 O(qm\log n)，前面因为形式混乱想不到什么十分优秀的合并方式，但是这个时候你前面直接写 O(\frac{nmq}{w}) 他就直接通过了，有点牛