题目链接

题目

题目描述

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 (A_i = A_i^2 mod 2018) 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

输出描述

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

输入

1
8
17 239 17 239 50 234 478 43
10
Q 2 6
C 2 7
C 3 4
Q 4 7
C 5 8
Q 6 7
C 1 8
Q 2 5
Q 3 4
Q 1 8

输出

Case #1:
779
2507
952
6749
3486
9937

题解

知识点：线段树，数论。

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

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

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

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

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

区间合并，有两种情况：

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

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

区间修改，有两种情况：

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

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

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

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

空间复杂度 (O(n))

代码

#include 
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  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 sum;
        int pos;
        bool lp;
    };
    struct F {
        int cnt;
    };
    int n;
    vector node;
    vector lazy;

    void push_up(int rt) {
        node[rt].lp = node[rt > 1;
        update(rt > 1;
        return query(rt  &src) { init(src); }

    void init(const vector &src) {
        assert(src.size() >= 2);
        n = src.size() - 1;
        node.assign(n  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 > n;
    vector a(n + 1);
    for (int i = 1;i > 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 > t;
    for (int i = 1;i 

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net