神秘扩展欧拉定理 + 均摊线段树。
题意：维护一个长度为 $n$ 的序列 $a$，修改是对 $[l, r]$ 将 $a_i$ 变为 $c ^ {a_i}$，或者询问 $\sum_{i = l} ^ r a_i$，输出 $\bmod p$ 的答案就可。$n, c$ 开始给定，$n, q\times 5\times 10 ^ 4$，$p\leq 10 ^ 8$。
显然 $a_i$ 的值仅和 $a_i$ 的初始值以及修改操作覆盖的次数有关。看到如此庞大的数，考虑扩展欧拉定理：$a ^ n\equiv a ^ {n\bmod \varphi(p) + \varphi(p)}\pmod p$，这时需要保证 $n\geq \varphi(p)$。
如果不操作，那么和 $a_i\bmod p$ 的值有关；如果操作一次，和 $a_i\bmod \varphi(p)$ 有关；如果操作两次，即 $c ^ {a_i}\bmod \varphi(p)$ 有关，即 $a_i\bmod \varphi(\varphi(p))$ 有关……这样下去，当 $\varphi(\varphi…(p)) = 1$ 的时候，这个答案和 $a_i$ 和操作次数都没有关了，它变成了一个定值（和操作次数无关是因为再操作相当于修改 $a_i$，没有什么用了）。
这样我们只需要维护前几次操作。大概是多少次呢？
结论：该深度为 $O(\log p)$ 级别。
证明：对于偶数来说，$\varphi(p)\leq \dfrac p2$；对于奇数来说，$2|\varphi(p)$，可以由 $\varphi(p)$ 的定义式得到。
这样我们就只需要暴力计算前 $O(\log n)$ 项即可。计算由于是暴力计算，而且不能利用前面的信息，只能依次按照原式计算。时间复杂度 $O(n\log ^ 3 n + q\log n)$，不太能过。
注意到我们的一个 $\log$ 是来自于快速幂的，但是容易发现底数只有一种，模数只有 $O(\log p)$ 种，于是光速幂预处理，可以做到 $O(n\log ^ 2 n + q\log n + \sqrt q\log p)$，可以通过。
注意扩展欧拉定理只能在 $n\geq \varphi(p)$ 时才能使用，所以需要判断指数是否 $\geq \varphi(p)$。
1 | struct LPow { |