P4681 [THUSC2015]平方运算

简要题意

给定一个序列，区间 .map([](int x) { x = x * x % p; });，区间求和。
p 给定，为小质数。\(N,M\le 105\)。

题解

而把一个数看作一个点，向其平方取模连一条边，则最终必然构成一个基环森林，注意到 \(P\)
很小，每个数经过至多 \(11\) 次迭代之后就会进入环中。对于一个区间，如果区间中的每个元素都已经在环里，则区间所有元素所在环的大小的 \(\operatorname{lcm}\)，即为区间的循环节。而对于题目给出的 \(P\)，\(\operatorname{lcm}\le 60\)，记为 \(C\)。

先考虑初始是每个元素都在环内的时候怎么做：发现可以用线段树维护，对于每个区间，我们可以直接维护该区间的一个完整循环节，以及当前在循环节内的位置 \(now\)，则如果要对整个区间进行 \(k\) 次修改，则直接让 \(now\) 向前移动 \(k\) 即可，故可以 \(O(1)\) pushdown，如果一个区间的子区间被修改了，那么在 pushup 的时候直接根据两个子区间的循环节算出当前区间的循环节即可，复杂度 \(O(C)\)。

如果一个区间内包含不在环内的元素，则无法维护循环节，我们只维护当前区间的和，需要 pushdown 时暴力递归向子区间 pushdown。由于每个元素经过至多 \(S=11\)
次操作后进入环，简单均摊分析发现这一部分增添的复杂度是 \(O(nSlogn)\) 的。

总时间复杂度 \(O(nlogn(C+S))\) 可以通过。

对于循环移位维护一个循环节和当前位置的指针是十分显然的。