題目連結

題目

題目描述

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 < 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

輸入

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 <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;
}