NC17383 A Simple Problem with Integers

题目

题目描述

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

输出描述

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

输出

题解

知识点：线段树，数论。

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

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

区间合并，有两种情况：

子区间都进入循环，则区间进入循环，顺序遍历子区间对应的循环值，并将和更新到区间的 \(sum\ 。

区间修改，有两种情况：

区间已进入循环，则直接平移 \(pos\ 即可。

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

空间复杂度 \(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;
}

编程笔记 » NC17383 A Simple Problem with Integers

NC17383 A Simple Problem with Integers

题目

题解

代码

相关文章

Hi，您需要填写昵称和邮箱！