妙妙 Tricky 题。
题目大意
给定序列 \(\{a_n\}\)，有 \(q\) 次操作，你需要支持：
- 区间除以 \(v\)。
- 区间按位与上 \(v\)。
- 查区间和。
数据范围：\(a_i \le 2^{128}\)，\(n \le 3 \times 10^5, q \le 2 \times 10^5\)。
思路
下面设 \(w\) 为 \(a_i\) 在二进制下的最大位数，即 \(128\)。
显然有一个暴力的做法：直接上势能线段树，维护一个区间是否全为 \(0\)。算一下每个位置会被处理几次，最多被除 \(w\) 次，每次除法之后可能会有些位变成 \(1\)，又有 \(w\) 次。那总体就是 \(w^2\) 次，复杂度 \(O(n \log n w^2)\)，可以过 Sub 2, 4 两档特殊性质。
上述做法看起来很没优化的前途，那考虑维护 tag 吧，因为要算 sum 所以除法的 tag 很难维护，不妨考虑维护一个位置按位与了多少。那么记 \(S_i\) 表示这个区间有多少数第 \(i\) 位为 \(1\)，和就是 \(\sum_i 2^iS_i\)。每次下放标记和上传 \(S\) 的复杂度都是 \(O(w)\) 的，那总的就是 \(O(q \log n w + nw^2)\)，还是过不了。
继续优化，一个性质是 \(S_i \le n\)，把 \(S_i\) 以二进制形式写成一个表格：第 \(i\) 行第 \(j\) 列表示 \(S_i\) 二进制下第 \(j\) 位是否为 \(1\)。这个表格是 \(w \times (\log n)\) 的，于是考虑维护每一列的值，记第 \(i\) 列从上往下的值是 \(T_i\)，看一下现在能不能维护。
对于下放 tag 的操作，可以直接将 \(T_i\) 与其按位与，复杂度 \(O(\log n)\)。
对于上传 \(T_i\) 的操作，可以模拟二进制加法，复杂度也是 \(O(\log n)\)。
并且区间的和也等于 \(\sum_i T_i 2^i\)，同样 \(O(\log n)\) 算出。
于是分析一下现在的复杂度，对于线段树上的一个点，我最多遍历 \(O(w)\) 遍，这一个点上传的复杂度是 \(T(n) = 2T(n / 2) + \log n = O(n)\) 的。所以复杂度变为 \(O(q \log^2 n + nw)\)，可以通过（但是需要极其逆天的卡常）。
好像还有更能扩展的 WBLT 做法，奈何蒟蒻不会 WBLT，只能咕咕了！