P8878 题解

joke3579 · 2022-12-12 10:17:21 · 题解

由于值域较小，考虑一个值域相关的算法。

对于每次操作，我们可以预先算出在该操作下每个 i 会变成的数字 f(i)。可以发现 f 是一个值域到自身的映射。映射的复合显然满足结合律，我们可以将区间进行 f_i 映射作为信息，使用线段树维护。

预处理 f_i^j \bmod p，这样可以在读入时以 O(V) 的复杂度计算映射，其中 V 是值域，该题中为 100。
随后以标记合并方式维护即可。标记合并的复杂度为 O(V)。

因此我们可以在 O(Vn\log n) 的复杂度内在线处理所有操作。

采用分块可以获得复杂度 O(n\sqrt{nV})，在本题的表现更优秀些。

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, R = 105;
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
int n, q, a[N], l, r, k, p, c, f[R][R][R];

struct permu {
    static const int len = 100;
    int p[R];
    permu() { iota(p, p + R, 0); }
    int operator[] (const int &i) const { return p[i]; }
    int &operator[] (const int &i) { return p[i]; }
    permu &operator *= (const permu &rhs) {
        for (int i = 0; i <= len; i++)
            p[i] = rhs[p[i]];
        return *this;
    }
    permu operator* (const permu &rhs) const {
        permu _(*this);
        return _ *= rhs;
    }
} id, per;

struct SMT {
    #define ls (p << 1)
    #define rs (p << 1 | 1)

    permu tr[N << 2];
    inline void ps_d(const int& p) {
        tr[ls] *= tr[p];
        tr[rs] *= tr[p];
        tr[p] = id;
    }
    void assign(int p, int l, int r, int L, int R, const permu& pr) {
        if (L <= l and r <= R) {
            tr[p] *= pr;
            return;
        } ps_d(p); int mid = l + r >> 1;
        if (L <= mid) assign(ls, l, mid, L, R, pr);
        if (mid < R) assign(rs, mid+1, r, L, R, pr);
    }
    void print(int p, int l, int r) {
        if (l == r) {
            printf("%d ", tr[p][a[l]]);
            return;
        } ps_d(p); int mid = l + r >> 1;
        print(ls, l, mid);
        print(rs, mid+1, r);
    }

    #undef rs
    #undef ls
} T;

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    rep(i,2,100) rep(j,1,100) f[1][i][j] = 1;
    rep(i,2,100) rep(j,1,100) {
        f[i][j][1] = (f[i - 1][j][1] + f[i - 2][j][1]) % j;
        rep(k,2,100) f[i][j][k] = f[i][j][k - 1] * f[i][j][1] % j;
    }
    while (q--) {
        cin >> l >> r >> k >> p >> c;
        rep(i,0,100) per[i] = (f[i][p][k] + c) % p;
        T.assign(1, 1, n, l, r, per);
    }
    T.print(1, 1, n);
}