标签：

「JSOI2013」贪心的导游

传送门

多次询问区间内%一个数的最大值 我们不妨事设这个数为M_sea

值域对照小所以考虑分块维护。

我们不雅察看到对付给定的一个 \(p\) ，函数 \(y = x \% p\) 是分段的且在各段内递增，所以我们可以先分块，记一下每个块内小于即是某个数的最大值，记为 \(g_i\) ，那么我们显然是要在所有的 \(i = kp - 1, k \ge 1\) 中盘问 \(g_i\) 并减失会被 % 失的部分，那么我们就可以预措置惩罚惩罚出一个块内的答案了，然后盘问的时候暴力查就是了。

#include <cstring> #include <cstdio> #include <cmath> #define rg register #define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout) template < class T > inline void swap(T& a, T& b) { T t = a; a = b; b = t; } template < class T > inline T max(T a, T b) { return a > b ? a : b; } template < class T > inline void read(T& s) { s = 0; int f = 0; char c = getchar(); while ('0' > c || c > '9') f |= c == '-', c = getchar(); while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar(); s = f ? -s : s; } const int _ = 1e6 + 5, __ = 1e3 + 5; int n, q, a[_], m, pos[_], f[__][__], g[_]; int main() { #ifndef ONLINE_JUDGE file("cpp"); #endif read(n), read(q), m = sqrt(1.0 * n); for (rg int i = 1; i <= n; ++i) read(a[i]), pos[i] = (i - 1) / m + 1; for (rg int i = 1; i <= pos[n]; ++i) { memset(g, 0, sizeof g); for (rg int j = (i - 1) * m + 1; j <= i * m && j <= n; ++j) g[a[j]] = a[j]; for (rg int j = 1; j <= 1000; ++j) if (!g[j]) g[j] = g[j - 1]; for (rg int j = 1; j <= 1000; ++j) { for (rg int k = j; k <= 1000; k += j) f[i][j] = max(f[i][j], g[k - 1] - (k - j)); f[i][j] = max(f[i][j], g[1000] % j); //这句话我也不知道为什么要加但是确实是加了就过了不加就WA } } for (rg int l, r, p, ans; q--; ) { read(l), ++l, read(r), ++r, read(p), ans = 0; if (l > r) swap(l, r); if (pos[l] == pos[r]) for (rg int i = l; i <= r; ++i) ans = max(ans, a[i] % p); else { for (rg int i = pos[l] + 1; i <= pos[r] - 1; ++i) ans = max(ans, f[i][p]); for (rg int i = l; i <= pos[l] * m; ++i) ans = max(ans, a[i] % p); for (rg int i = (pos[r] - 1) * m + 1; i <= r; ++i) ans = max(ans, a[i] % p); } printf("%d\n", ans); } return 0; }

「JSOI2013」贪心的导游

，