提供一种需要卡常的分块写法。

首先看到 popcount 操作，便可以自然而然的想到在值域上做文章。

首先因为 \(popcount(x) \leq \log x\)。

所以可以想到对于一个序列来说，进行一次 popcount 操作后至多有 \(\log V\) 个不同的数字。

并且在对这个区间进行全局操作时不同数的数量不增。

因此考虑分块。

块内最开始用 tag 记录加法操作。

对于块内如果有整块 popcount 操作则转换成 pair 记录每个值都变成了什么。

类似于阈值分治的思想，不同类型的数据不同处理。

这样做复杂度是 \(O(q \sqrt n \log V)\) 。

会 T 得很惨。

不过还能改进。

这样做在保持分块的情况下不会写线段树的标记只能改进 popcount。

所以我们用 __builtin_popcounll 函数。

所以我们这样写：

inline int popcount(int n){    return __builtin_popcountll(n);}

如此再加上一定卡常就可以过了。

代码比较丑，我贴一个剪切版在这：代码

不过这样为什么可以过呢？

因为这个函数内部用自带的表以及二分实现，虽然都是 \(\log\) 量级，但是二分理论上很难跑满。