「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);

                //这里是为了防止一些极端情况比如说你一个块里面只有一个999

	    }

    }

    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;

}