自动搬运

查看原文

来自洛谷，原作者为

	joke3579 **

搬运于2025-08-24 22:43:21，当前版本为作者最后更新于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);
}