自动搬运

查看原文

来自洛谷，原作者为

	xgzc 苔花如米小，也学牡丹开。

搬运于2025-08-24 22:17:50，当前版本为作者最后更新于2020-03-21 21:57:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分块，设 $f_{i, j}$ 表示第 $i$ 块中 $\bmod j$ 的最大值。

预处理时枚举每一个块，块内预处理出数组 $g_i$ 表示 $\leq i$ 的最大值，然后根据 $x \bmod p$ 分段单调递增的特性求出 $f_{i, j}$。

询问则是经典的分块套路，即整块直接得到答案，零散块暴力。

设块长为 $B$，则时间复杂度为 $\mathcal{O} (\frac {np \log p}B + n + m(B + \frac nB))$。

当取块长 $B = \mathcal O(\sqrt n)$ 时，时间复杂度为 $\mathcal O((p \log p + m) \sqrt n)$。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>

inline int read()
{
	int data = 0, w = 1; char ch = getchar();
	while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
	if (ch == '-') w = -1, ch = getchar();
	while (ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
	return data * w;
}

const int N(1e6 + 10), Mod(1e3 + 10), P(1000);
int n, m, a[N], f[Mod][Mod], g[Mod], bel[N], L[N], R[N], Len;

int main()
{
	n = read(), m = read(), Len = sqrt(n);
	for (int i = 1; i <= n; i++) a[i] = read();
	for (int i = 1; i <= n; i++) bel[i] = (i - 1) / Len + 1;
	for (int i = 1; i <= n; R[bel[i]] = i, i++) if (!L[bel[i]]) L[bel[i]] = i;
	for (int i = 1; i <= bel[n]; i++)
	{
		memset(g, 0, sizeof g);
		for (int j = L[i]; j <= R[i]; j++) g[a[j]] = a[j];
		for (int j = 1; j <= P; j++) if (!g[j]) g[j] = g[j - 1];
		for (int j = 1; j <= P; j++)
		{
			f[i][j] = std::max(f[i][j], g[P] % j);
			for (int k = j; k <= P; k += j)
				f[i][j] = std::max(f[i][j], g[k - 1] % j);
		}
	}
	while (m--)
	{
		int l = read() + 1, r = read() + 1, p = read(), ans = 0;
		if (l > r) std::swap(l, r);
		if (bel[l] == bel[r])
			for (int i = l; i <= r; i++) ans = std::max(ans, a[i] % p);
		else
		{
			for (int i = bel[l] + 1; i <= bel[r] - 1; i++)
				ans = std::max(ans, f[i][p]);
			for (int i = l; bel[i] == bel[l]; i++) ans = std::max(ans, a[i] % p);
			for (int i = r; bel[i] == bel[r]; i--) ans = std::max(ans, a[i] % p);
		}
		printf("%d\n", ans);
	}
	return 0;
}