NC17383 A Simple Problem with Integers

题目链接

题目描述

You have N integers A1, A2, ... , AN. You are asked to write a program to receive and execute two kinds of instructions:

1. C a b means performing Ai=A2imod2018Ai=Ai2mod2018 for all Ai such that a ≤ i ≤ b.
2. Q a b means query the sum of Aa, Aa+1, ..., Ab. Note that the sum is not taken modulo 2018.

输入描述

The first line of the input is T(1≤ T ≤ 20), which stands for the number of test cases you need to solve.
The first line of each test case contains N (1 ≤ N ≤ 50000).The second line contains N numbers, the initial values of A1, A2, ..., An. 0 ≤ Ai < 2018. The third line contains the number of operations Q (0 ≤ Q ≤ 50000). The following Q lines represents an operation having the format "C a b" or "Q a b", which has been described above. 1 ≤ a ≤ b ≤ N.

输出描述

For each test case, print a line "Case #t:" (without quotes, t means the index of the test case) at the beginning.
You need to answer all Q commands in order. One answer in a line.

示例1

输入

1817 239 17 239 50 234 478 4310Q 2 6C 2 7C 3 4Q 4 7C 5 8Q 6 7C 1 8Q 2 5Q 3 4Q 1 8

输出

Case #1:7792507952674934869937

知识点：线段树，数论。

显然，区间同余是没法直接运用懒标记的，我们需要找到能使用懒标记的结构。

容易证明， Ai=A2imod2018Ai=Ai2mod2018 运算在有限次操作后一定会进入一个循环节，且长度的最小公倍数不超过 66 。而且可以发现，进入循环的需要的操作次数其实很少。

注意到，进入循环的区间可以预处理出所在循环节的所有值，并用一个指针指向当前值即可，随后每次修改相当于在环上移动指针，显然可以懒标记。对于未进入循环节的区间，先采用单点修改，直到其值进入循环节。

因此，我们先预处理枚举 [0,2018)[0,2018) 所有数是否在循环节内，用 cyccyc 数组记录每个数的所在循环节的长度。如果某数的循环节长度非 00 ，则其为循环节的一部分。我们对循环节长度取最小公倍数 cyclcmcyclcm，以便统一管理。

对此，区间信息需要维护区间是否进入循环 lplp 、区间循环值 sumsum 数组、区间值指针 pospos 。若未进入循环，则值存 sum[0]sum[0] ，且 pos=0pos=0 ；若进入循环，则 sumsum 存循环的各个值， pospos 指向当前值的位置。

区间合并，有两种情况：

1. 存在子区间未进入循环，则区间未进入循环，最终值由子区间当前值相加。
2. 子区间都进入循环，则区间进入循环，顺序遍历子区间对应的循环值，并将和更新到区间的 sumsum 。

区间修改只需要维护指针平移总量 cntcnt 。

区间修改，有两种情况：

1. 区间未进入循环，则继续递归子区间，直到单点修改。每次单点修改后，检查是否进入循环，若进入循环，则预处理出 sumsum 。
2. 区间已进入循环，则直接平移 pospos 即可。

标记修改，直接加到标记上即可，可以模 20182018。注意，当且仅当区间进入循环后标记才有意义，但事实上，未进入循环的区间标签始终为 00 ，对修改没有影响，无需特判。

这道题实际上是洛谷P4681的弱化版，我这里使用了通解的做法，比只针对这道题的做法要慢一点。只针对这道题的做法是基于另一个更进一步的结论，所有数字在 66 次操作之后一定进入循环，那么只需要记录一个单点是否操作 66 次作为检查条件即可，省去了枚举 [0,2018)[0,2018) 所有数字的循环节长度的时间。

时间复杂度 O((n+m) logn)O((n+m)logn)

空间复杂度 O(n)O(n)

#include <bits/stdc++.h>using namespace std;using ll = long long; const int P = 2018;int cyc[P];int cyclcm; void init_cyc() { cyclcm = 1; for (int i = 0;i < P;i++) { cyc[i] = 0; vector<int> vis(P); for (int j = 1, x = i;;j++, x = x * x % P) { if (vis[x]) { if (x == i) { cyc[i] = j - vis[i]; cyclcm = lcm(cyclcm, cyc[i]); } break; } vis[x] = j; } }} class SegmentTreeLazy { struct T { array<int, 6> sum; int pos; bool lp; }; struct F { int cnt; }; int n; vector<T> node; vector<F> lazy; void push_up(int rt) { node[rt].lp = node[rt << 1].lp && node[rt << 1 | 1].lp; node[rt].pos = 0; if (node[rt].lp) for (int i = 0, l = node[rt << 1].pos, r = node[rt << 1 | 1].pos; i < cyclcm; i++, ++l %= cyclcm, ++r %= cyclcm) node[rt].sum[i] = node[rt << 1].sum[l] + node[rt << 1 | 1].sum[r]; else node[rt].sum[0] = node[rt << 1].sum[node[rt << 1].pos] + node[rt << 1 | 1].sum[node[rt << 1 | 1].pos]; } void push_down(int rt) { (node[rt << 1].pos += lazy[rt].cnt) %= cyclcm; (lazy[rt << 1].cnt += lazy[rt].cnt) %= cyclcm; (node[rt << 1 | 1].pos += lazy[rt].cnt) %= cyclcm; (lazy[rt << 1 | 1].cnt += lazy[rt].cnt) %= cyclcm; lazy[rt].cnt = 0; } void check(int rt) { node[rt].pos = 0; if (cyc[node[rt].sum[0]]) { node[rt].lp = 1; for (int i = 1;i < cyclcm;i++) node[rt].sum[i] = node[rt].sum[i - 1] * node[rt].sum[i - 1] % P; } else node[rt].lp = 0; } void update(int rt, int l, int r, int x, int y) { if (r < x || y < l) return; if (x <= l && r <= y && node[rt].lp) { ++node[rt].pos %= cyclcm; ++lazy[rt].cnt %= cyclcm; return; } if (l == r) { node[rt].sum[0] = node[rt].sum[0] * node[rt].sum[0] % P; check(rt); return; } push_down(rt); int mid = l + r >> 1; update(rt << 1, l, mid, x, y); update(rt << 1 | 1, mid + 1, r, x, y); push_up(rt); } int query(int rt, int l, int r, int x, int y) { if (r < x || y < l) return 0; if (x <= l && r <= y) return node[rt].sum[node[rt].pos]; push_down(rt); int mid = l + r >> 1; return query(rt << 1, l, mid, x, y) + query(rt << 1 | 1, mid + 1, r, x, y); } public: SegmentTreeLazy(const vector<int> &src) { init(src); } void init(const vector<int> &src) { assert(src.size() >= 2); n = src.size() - 1; node.assign(n << 2, { {},0,0 }); lazy.assign(n << 2, { 0 }); function<void(int, int, int)> build = [&](int rt, int l, int r) { if (l == r) { node[rt].sum[0] = src[l]; check(rt); return; } int mid = l + r >> 1; build(rt << 1, l, mid); build(rt << 1 | 1, mid + 1, r); push_up(rt); }; build(1, 1, n); } void update(int x, int y) { update(1, 1, n, x, y); } int query(int x, int y) { return query(1, 1, n, x, y); }};//* 朴素操作开销太大（array复制），因此全部展开 bool solve() { int n; cin >> n; vector<int> a(n + 1); for (int i = 1;i <= n;i++) cin >> a[i]; init_cyc(); SegmentTreeLazy sgt(a); int m; cin >> m; while (m--) { char op; int l, r; cin >> op >> l >> r; if (op == 'C') sgt.update(l, r); else cout << sgt.query(l, r) << '\n'; } return true;} int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; for (int i = 1;i <= t;i++) { cout << "Case #" << i << ":" << '\n'; if (!solve()) cout << -1 << '\n'; } return 0;}