我是傻子
给定一个长度为 $n \le 10^5$ 的序列 $a_i \le 10^5$ ， $m \le 10^5$ 次询问，给定 $l, r, p(1 \le l \le r \le n, p \le 10^9)$ ，求区间 $[l, r]$ 的所有子序列分别去重后的和 $\mod p$
思路
看出题人想 $\sqrt{n}$ 算法
先拆贡献，对于区间 $[l, r]$ ，若数字 $x$ 在区间内出现了 $cnt$ 次，那么它的贡献就是 $x * (2^{r - l + 1} - 2^{r - l + 1 - cnt})$ （就是所有子序列 - 不存在 $x$ 的子序列）
由于要维护动态 $cnt$ ，马上想到莫队（完了，我不擅长莫队 但仔细一想我好像没有擅长的欸 ），直接套莫队板子就可以 $O(n \sqrt{n})$ 维护 $cnt$
但每次询问我们都要把每个 $x$ 算一个贡献，最坏要把整个区间扫完，就又挂了
这里有不同的解法， wfy巨佬说可以平衡规划，把整个序列出现次数 $\ge \sqrt{n}$ 的数字记下来，然后在莫队中把出现次数相同的数都加到一起（反正它们都要乘 $(2^{r - l + 1} - 2^{r - l + 1 - cnt})$ ），每次计算时不枚举 $x$ 而枚举 $cnt$ ，此时 $cnt$ 必定 $\le \sqrt{n}$ ，因为大于的我们都调记录了，时间就是 $O(n \sqrt{n})$
但蒟蒻我比较弱，只能考虑暴力上数据结构，还是把出现次数相同的数都加到一起，然后枚举 $cnt$ ，但发现很多 $cnt$ 里一个数字都没有，于是考虑用一个链表存储有意义的 $cnt$ （不能用 STL 因为它删除是 $O(n)$ 的，建议手写双向链表），这样就不会枚举到无用的 $cnt$ ，考虑到不同的 $cnt$ 最多只有 $\sqrt{n}$ 级（因为 $cnt$ 代表是数的个数，而 $1 + 2 + 3 + … + x = \frac{x (x - 1)}{2} \le n$ ），所以时间就也是 $O(n \sqrt{n})$
最后一个问题是 $2^{r - l + 1 - cnt}$ ，快速幂计算显然每次 $O(\log n)$ ，不可接受（ lxl 的题还想 $\log$ 算法？），考虑光速幂，每次询问 $\sqrt{n}$ 预处理， $O(1)$ 解决每次计算（这里注意，由于指数最大是 $n$ ，所以只用处理到 $\sqrt{n}$ ，而不是 $\sqrt{p}$ ，且也不用 $\mod \varphi(p)$ ）
总时间 $O(n \sqrt{n})$
代码
我光速幂打挂了三次……，一共就两个函数……（记得 $B \ge \sqrt{n}$ ）
我的打法常数略大，但反正可过
如果你被卡常了，这里分享一些卡常技巧：
- 快读/快输
- 别万能头
-
inline - 把答案用
__int128_/long double存，中间不取模，最后在统一取模（不会爆） - 光速幂用进制拆分
- 调块长（但一点要大于 $\sqrt{n}$ ）
反正我没被卡，就一个都不想用了
1 |
|