• \(\text{Ynoi2015}\) 盼君勿忘

题目：

一个序列，每次查询给定 \(l,r,p\)，求区间 \([l,r]\) 中所有子序列分别去重后的和 \(\bmod\ p\)。

\(n\le 10^5\)。

---

题解：

去重转化成贡献。

对于在区间 \([l,r]\) 中的一个值 \(x\) 出现 \(k\)，则其贡献为 \(x(2^{r-l+1}-2^{r-l+1-k})\)。

所以对于 \(S_k\) 表示所有出现次数为 \(k\) 的数的和，区间总贡献为 \(\displaystyle \sum_{i=1}^{r-l+1}S_i(2^{r-l+1}-2^{r-l+1-i})\)。

考虑如何去在转移中计算 \(S_k\)。

直接用莫队去统计，但是如果直接如上述式子中枚举 \(k\) 效率退化，考虑如何快速取出所有满足条件的 \(k\)。

考虑一种支持插入，删除，遍历的数据结构，那么显然可以使用链表或者 unorded_map 来维护 \(k\)。

对于 \(2^{r-l+1}-2^{r-l+1-k}\) 直接光速幂，\(O(\sqrt n)\) 的预处理算出 \(pw1_i=2^i,pw2_i=2^{i\sqrt n}(1\le n\le \sqrt n)\) 直接做到 \(O(1)\) 查询。

总时间复杂度 \(O(n\sqrt m+m\sqrt n)\)，空间复杂度 \(O(n+m)\)。