いずれその陽は落ちるとしても

题意：

给一个序列 $a_1, a_2, \dots, a_n$ ， $m$ 次查询区间 $[l_i, r_i]$ 所有子序列去重之和之和模 $p_i$ 。

$1 \leq n, m, a_i \leq 10 ^ 5, 1 \leq p \leq 10 ^ 9$ 。

题解：

考虑每个子区间由每种数出现的第一次进行贡献。

对一个数值 $v$ 和区间 $[l, r]$ ，令 $pre_x$ 为 $a_x$ 在这个区间内在它之前同值前面出现的次数， $len := r - l + 1$ ，显然某个 $a_x = v$ 的贡献为：

$$2 ^ {len - pre(v) - 1} v$$

设 $cnt(l, r, v)$ 为 $v$ 在 $[l, r]$ 出现的次数，那么所有值为 $v$ 的位置的贡献为：

$$\sum 2 ^ {len - 1} v + 2^{len - 2} v + \dots + 2^{len - cnt(l, r, v)} v = 2 ^ {len} v - 2 ^{len - cnt(l, r, v)} v $$

那么所有数的贡献为：

$$2 ^ {len} \sum_{v \in \{a_l, a_{l + 1}, \dots, a_r\}} v - \sum_{v \in \{a_l, a_{l + 1}, \dots, a_r\}} 2^{len - cnt(l, r, v)} v $$

注意到 $\sum v \leq 10^{10}$ ，前者直接维护本质不同的数的和即可，在莫队的过程中很容易维护。

后者在模数改变的时候似乎仍然是 $\mathcal{O}(len)$ 的。

然而 $\sum cnt_x = n$ 这个性质可以导出推论，即本质不同的 $cnt_x$ 的个数不多于 $2 \sqrt n$ 个（大于 $\sqrt n$ 的 $cnt$ 至多 $\sqrt n$ 个不然和会大于 $n$ ）。

后半个式子按照 $cnt$ 分类：

$$\sum_{cnt} 2 ^ {len - cnt} \sum_{cnt(l, r, v) = cnt} v $$

统计每个出现次数的权值和在莫队过程中可以 $\mathcal{O}(1)$ 插入删除 $\mathcal{O}(\sqrt n)$ 项枚举上面的和式。

那么复杂度就是 $\mathcal{O}(m \sqrt n \log n+ n \sqrt m)$ 的。

然后求幂次的过程仍然能优化。

现在需要在每次查询中求出所有 $2^{cnt}$ ，暴力快速幂是 $\mathcal{O}(\sqrt n \log n)$ 的。但是可以根号分治优化到 $\mathcal{O}(\sqrt n)$。

把值域按照 $\sqrt n$ 分块，求块头，块内的值是一个 $< \sqrt n$ 的幂次。两者都是能在 $\mathcal{O}(\sqrt n)$ 的时间内进行预处理，然后支持 $\mathcal{O}(1)$ 查询的。

具体地，预处理 $2^0, 2^1, \dots, 2^{\sqrt n - 1}$ ，预处理 $2^{\sqrt n}, 2 ^ {2 \sqrt n}, \dots, 2 ^ {\lfloor \frac{n}{\sqrt n} \rfloor \sqrt n}$ ，然后 $cnt = k \sqrt n + r$ 。

这样子复杂度降低到了 $\mathcal{O}(m \sqrt n + n \sqrt m)$ 。