P4681 [THUSC 2015] 平方运算 Solution

Description

给定序列 $a=(a_1,a_2,\cdots ,a_n)$ 和常数 $p$ ，有 $m$ 个操作，分以下两种：

• $\mathrm{modify}(l,r)$：对每个 $i\in [l,r]$ 执行 $a_i\leftarrow a_i^2\mathrm{mod}p$.
• $\mathrm{query}(l,r)$：求 $\sum _{i=l}^r{a}_i$.

Limitations

$1\le n,m\le 10^5$
$0\le a_i<p$
p ∈ { 233 , 2332 , 5 , 8192 , 23 , 45 , 37 , 4185 , 5850 , 2975 , 2542 , 2015 , 2003 , 2010 , 4593 , 4562 , 1034 , 5831 , 9905 , 9977 } p \in {\{233,2332,5,8192,23,45,37,4185,5850,2975,2542,2015,2003,2010,4593,4562,1034,5831,9905,9977\}} p∈{233,2332,5,8192,23,45,37,4185,5850,2975,2542,2015,2003,2010,4593,4562,1034,5831,9905,9977}
$2\text{s},250\text{MB}$

Solution

$\mathrm{modify}$ 操作不能直接标记，也不能直接暴力改.
但是模意义下的平方运算显然是有周期性的，打表发现，在 $p$ 取给定数时，所有数的周期的 $\mathrm{lcm}$ 不大于 $60$，并且每个数平方不超过 $11$ 次就会进入循环节.
考虑在线段树上维护：

• $cycle$：这个区间内的数是否全部进入循环节.
• $su{m}_i$：全部进入循环节的情况下，每个数平方 $i$ 次后的和.
• $now$：当前区间的和在循环节的第几个位置.
• $tag$：标记，表示儿子需要平方几次.

特别地，如果没有全部进入循环节，则用 $su{m}_0$ 来记录和.
然后进入循环节的直接跳，没有的就暴力改（因为不超过 $11$ 次）.
注意当一个数进入循环节时，需要将 $su{m}_i$ 全部算出.
剩下就没什么了，一开始时把每个数平方的周期长度全算一遍即可.

Code

$4.27\text{KB},9.45\text{s},193.55\text{MB}\text{(in total, C++ 20 with O2)}$

// Problem: P4681 [THUSC 2015] 平方运算
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4681
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;template<class T>
bool chmax(T &a, const T &b){if(a < b){ a = b; return true; }return false;
}template<class T>
bool chmin(T &a, const T &b){if(a > b){ a = b; return true; }return false;
}struct Node {int l, r;bool cycle;int now, tag;array<i64, 60> sum;
};
inline int ls(int u) { return 2 * u + 1; }
inline int rs(int u) { return 2 * u + 2; }struct SegTree {vector<Node> tr;vector<int> P, vis;int M, mod;inline SegTree() {}inline SegTree(const vector<int>& a, int _mod):P(_mod), vis(_mod, -1), M(1), mod(_mod) {for (int i = 0; i < mod; i++) get_loop(i);for (int i = 0; i < mod; i++)if (P[i] != 0) M = lcm(M, P[i]);const int n = a.size();tr.resize(n << 2);build(0, 0, n - 1, a);}inline void get_loop(int x) {for (int i = 0, y = x; ; i++, y = y * y % mod) {if (vis[y] != -1) {P[y] = i - vis[y];break;}else vis[y] = i;}for (int y = x; vis[y] != -1; y = y * y % mod) vis[y] = -1;}inline void upd(int u) {if (P[tr[u].sum[0]] != 0) {for (int i = 1; i < M; i++) tr[u].sum[i] = tr[u].sum[i - 1] * tr[u].sum[i - 1] % mod;tr[u].now = 0;tr[u].cycle = 1;}else tr[u].now = tr[u].cycle = 0;}inline void apply(int u, int k) {tr[u].tag = (tr[u].tag + k) % M;tr[u].now = (tr[u].now + k) % M;}inline void pushup(int u) {tr[u].cycle = tr[ls(u)].cycle && tr[rs(u)].cycle;tr[u].now = 0;if (!tr[u].cycle)tr[u].sum[0] = tr[ls(u)].sum[tr[ls(u)].now] + tr[rs(u)].sum[tr[rs(u)].now];else {int nowL = tr[ls(u)].now, nowR = tr[rs(u)].now;for (int i = 0; i < M; i++) {tr[u].sum[i] = tr[ls(u)].sum[nowL] + tr[rs(u)].sum[nowR];nowL = (nowL + 1) % M;nowR = (nowR + 1) % M;}}}inline void pushdown(int u) {if (tr[u].tag) {apply(ls(u), tr[u].tag);apply(rs(u), tr[u].tag);tr[u].tag = 0;}}inline void build(int u, int l, int r, const vector<int>& a) {tr[u].l = l;tr[u].r = r;if (l == r) {tr[u].sum[0] = a[l];tr[u].tag = 0;return upd(u);}const int mid = (l + r) >> 1;build(ls(u), l, mid, a);build(rs(u), mid + 1, r, a);pushup(u);}inline void square(int u, int l, int r) {if (l <= tr[u].l && tr[u].r <= r && tr[u].cycle) return apply(u, 1);if (tr[u].l == tr[u].r) {tr[u].sum[0] = tr[u].sum[0] * tr[u].sum[0] % mod;return upd(u);}const int mid = (tr[u].l + tr[u].r) >> 1;pushdown(u);if (l <= mid) square(ls(u), l, r);if (r > mid) square(rs(u), l, r);pushup(u);}inline i64 query(int u, int l, int r) {if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum[tr[u].now];const int mid = (tr[u].l + tr[u].r) >> 1;i64 res = 0;pushdown(u);if (l <= mid) res += query(ls(u), l, r);if (r > mid) res += query(rs(u), l, r);return res;}
};signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, m, p;scanf("%d %d %d", &n, &m, &p);vector<int> a(n);for (int i = 0; i < n; i++) scanf("%d", &a[i]);SegTree seg(a, p);for (int i = 0, op, l, r; i < m; i++) {scanf("%d %d %d", &op, &l, &r);l--, r--;if (op == 1) seg.square(0, l, r);else printf("%lld\n", seg.query(0, l, r));}return 0;
}