代码是半成品，调自闭了。

大概是一个暴力思路（不保证正确，复杂度比较劣，不保证能过（本来想试试，然后调自闭了），没写完，纯口嗨，错了不负责），学会了正解再来补好了。

---

考虑暴力，我们将二进制位拆成前 \(w-cnt\) 位和后 \(cnt\) 位。

这里只讨论 OR 和 XOR 的情况，AND 和 OR 类似。

我们考虑枚举前 \(w-cnt\) 位，先考虑 XOR：

散块的部分我们暴力，对于整块我们进行分类：

1. 空块。
2. 非空块。

对于 XOR 而言，\(i\to j\) 则 \(j\to i\)，于是相当于 swap（如果都被操作）

否则为 \(i\to j\)

若 \(i,j\) 均非空，则暴力，此时至少会减少一个非空块。

如果 \(j\) 为空，则直接将 \(j\) 这个块设为 \(i\) 即可。

显然一次操作最多增加两个非空块（由散块提供）

对于其中第二类情况，我们做 \(\mathcal O(2^{cnt})\) 的暴力即可，复杂度显然为 \(\mathcal O(q(2^{cnt}+2^{w-cnt}))\)，然后我们对于一个整块打一个 XOR 的标记即可。

对于 OR，我们仍然类似处理，现在考虑如何处理 OR 的标记。

我们考虑一个 sub pro，维护集合，支持 OR 和 XOR，每次操作后输出集合大小，\(q\le 10^7,w\le 10\)

可以这样做，我们维护一个长为 w 的数组，表示每个位有没有被 OR 1 过，每次如果增加了一个 OR 1 的位，我们就暴力重构，否则我们维护一个先 or 上 Z 再 xor 上 X 的标记即可。复杂度显然为 \(\mathcal O(q+w2^w)\)

于是对于 OR，我们仍然是散块暴力，非空 & 非空暴力，非空到空的类型则直接做上述算法即可。

显然每次重构，会增加 \(cnt\) 个标记，复杂度为 \(\mathcal O(q(cnt2^{cnt}+2^{w-cnt}))\)

可以在 \(\mathcal O(q\sqrt{w2^w})\) 的复杂度解决本题。

---

\(Code:\)

想欣赏 6kb 代码不能过手造样例吗？