题解 P6141 【[JSOI2013]贪心的导游】

xgzc · 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;
}