【2018 国庆雅礼 NOIP 培训】D1T1 养花

发表于

这里是题面

分块大法好！！！

首先，我们考虑当 k 确定的时候如何求答案, 显然对于所有形如 [ak,(a+1)k) 的 值域区间, 最大值一定是最优的。

进一步观察发现, 这样的区间总个数只有 klnk 个.，所以我们考虑分块,

那么我 们可以在 O(n+klnk) 的时间复杂度内处理出一个块对于任意 k 的答案. 询 问时复杂度是 O(mS) 的, 取 S =√klnk 可以达到最优复杂度 O(n√klnk)。

标程如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>

using std::vector;

typedef long long ll;

template <typename T> bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }

const int oo = 0x3f3f3f3f;

template <typename T> T read(T& x) {
    int f = 1; x = 0;
    char ch = getchar();
    for(;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    return x *= f;
}

const int B = 1000;
const int N = 100000;

int n, q;
int a[N + 5];
int lst[N + 5];
int ans[105][N + 5];

int main() {
	
    read(n); read(q);
    for(int i = 0; i < n; ++i) read(a[i]);

    int blks = (n-1) / B + 1;
    for(int i = 0; i < blks; ++i) {
        memset(lst, 0, sizeof lst);
        for(int j = i * B; j < (i+1) * B && j < n; ++j) lst[a[j]] = a[j];
        for(int j = 1; j <= N; ++j) chkmax(lst[j], lst[j-1]);
        for(int j = 1; j <= N; ++j) for(int k = 0; k <= N; k += j) chkmax(ans[i][j], lst[std::min(k + j - 1, N)] - k);
    }

    while(q--) {
        static int l, r, k;
        read(l), read(r), read(k);

        -- l, -- r;
        int x = (l / B) + 1, y = (r / B), res = 0;

        if(x == y + 1) {
            for(int i = l; i <= r; ++i) chkmax(res, a[i] % k);
        } else {
            for(int i = x; i < y; ++i) chkmax(res, ans[i][k]);
            for(int i = l; i < x*B; ++i) chkmax(res, a[i] % k);
            for(int i = r; i >=y*B; --i) chkmax(res, a[i] % k);
        }

        printf("%d\n", res);
    }

    return 0;
}