[SCOI2007] 降雨量

题意

给出若干个有记录的年份和对应降雨量。

对于每个询问 (Y, X)，判断这句话是否成立：

X 年是自 Y 年以来降雨量最多的

题意中的“最多”并不是通常的“大于等于”，而是：

rain[X] <= rain[Y]
对所有 Y < Z < X，都有 rain[Z] < rain[X]

由于有些年份没有记录，答案可能是：

true：一定成立
false：一定不成立
maybe：目前信息下无法确定

思路

先看一个最直接的朴素做法：

cpp

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200 + 5;

int n;
int year_arr[MAXN];
int rain_arr[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> year_arr[i] >> rain_arr[i];
    }

    int m;
    cin >> m;
    while (m--) {
        int y, x;
        cin >> y >> x;

        int pos_y = -1;
        int pos_x = -1;
        for (int i = 1; i <= n; i++) {
            if (year_arr[i] == y) {
                pos_y = i;
            }
            if (year_arr[i] == x) {
                pos_x = i;
            }
        }

        bool has_y = (pos_y != -1);
        bool has_x = (pos_x != -1);

        if (has_y && has_x) {
            bool ok = true;
            if (rain_arr[pos_x] > rain_arr[pos_y]) {
                ok = false;
            }
            for (int i = 1; i <= n; i++) {
                if (y < year_arr[i] && year_arr[i] < x && rain_arr[i] >= rain_arr[pos_x]) {
                    ok = false;
                }
            }

            if (!ok) {
                cout << "false\n";
                continue;
            }

            bool full = true;
            int cur = y;
            for (int i = pos_y; i <= pos_x; i++) {
                if (year_arr[i] != cur) {
                    full = false;
                    break;
                }
                cur++;
            }
            if (cur != x + 1) {
                full = false;
            }

            if (full) {
                cout << "true\n";
            } else {
                cout << "maybe\n";
            }
        }
        else if (has_y && !has_x) {
            bool bad = false;
            for (int i = 1; i <= n; i++) {
                if (y < year_arr[i] && year_arr[i] < x && rain_arr[i] >= rain_arr[pos_y]) {
                    bad = true;
                }
            }

            if (bad) {
                cout << "false\n";
            } else {
                cout << "maybe\n";
            }
        }
        else if (!has_y && has_x) {
            bool bad = false;
            for (int i = 1; i <= n; i++) {
                if (y < year_arr[i] && year_arr[i] < x && rain_arr[i] >= rain_arr[pos_x]) {
                    bad = true;
                }
            }

            if (bad) {
                cout << "false\n";
            } else {
                cout << "maybe\n";
            }
        }
        else {
            cout << "maybe\n";
        }
    }

    return 0;
}

brute.cpp 对每个询问直接扫描所有已知年份，找出落在 (Y, X) 中间的记录，再按定义判断。

这个做法的逻辑很适合帮助理解题意，也适合做小数据对拍。

真正优化时，先把题意翻成数学条件：

rain[X] <= rain[Y]
中间所有年份 Z 都满足 rain[Z] < rain[X]

于是每个询问的关键矛盾只剩一个：

(Y, X) 中间的已知年份里，是否存在某个年份的降雨量 >= rain[X]`

这就变成了一个静态区间最大值查询问题。

做法如下：

把所有已知年份按升序存下来
用 lower_bound 找到 Y、X 在记录数组中的位置
用 ST 表查询中间这段已知年份的最大降雨量
根据 Y、X 是否存在，分四种情况讨论

最重要的一类是 Y、X 都存在时：

若 rain[X] > rain[Y]，直接 false
若中间最大值 >= rain[X]，也直接 false
否则，若 Y..X 每一年都有记录，则结论被完全确定，输出 true
否则中间缺少年份，只能输出 maybe

其余三类情况本质上都是“已知数据没有形成矛盾就 maybe，形成矛盾就 false”。

代码

cpp

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50000 + 5;
const int LOG = 17;

int n;
int year_arr[MAXN];
int rain_arr[MAXN];
int lg2_arr[MAXN];
int st[LOG + 1][MAXN];

void build_sparse_table() {
    lg2_arr[1] = 0;
    for (int i = 2; i <= n; i++) {
        lg2_arr[i] = lg2_arr[i / 2] + 1;
    }

    for (int i = 1; i <= n; i++) {
        st[0][i] = rain_arr[i];
    }

    for (int k = 1; k <= LOG; k++) {
        int len = 1 << k;
        int half = len >> 1;
        for (int i = 1; i + len - 1 <= n; i++) {
            st[k][i] = max(st[k - 1][i], st[k - 1][i + half]);
        }
    }
}

int query_max(int l, int r) {
    if (l > r) {
        return -1;
    }
    int k = lg2_arr[r - l + 1];
    return max(st[k][l], st[k][r - (1 << k) + 1]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> year_arr[i] >> rain_arr[i];
    }

    build_sparse_table();

    int m;
    cin >> m;
    while (m--) {
        int y, x;
        cin >> y >> x;

        int pos_y = lower_bound(year_arr + 1, year_arr + n + 1, y) - year_arr;
        int pos_x = lower_bound(year_arr + 1, year_arr + n + 1, x) - year_arr;

        bool has_y = (pos_y <= n && year_arr[pos_y] == y);
        bool has_x = (pos_x <= n && year_arr[pos_x] == x);

        int left = pos_y;
        if (has_y) {
            left++;
        }

        int right = pos_x - 1;
        if (!has_x) {
            right = pos_x - 1;
        }

        int middle_max = query_max(left, right);

        if (has_y && has_x) {
            if (rain_arr[pos_x] > rain_arr[pos_y] || middle_max >= rain_arr[pos_x]) {
                cout << "false\n";
                continue;
            }

            // 若区间内每一年都有记录，则结论已经被完全确定。
            if (pos_x - pos_y == x - y) {
                cout << "true\n";
            } else {
                cout << "maybe\n";
            }
        }
        else if (has_y && !has_x) {
            if (middle_max >= rain_arr[pos_y]) {
                cout << "false\n";
            } else {
                cout << "maybe\n";
            }
        }
        else if (!has_y && has_x) {
            if (middle_max >= rain_arr[pos_x]) {
                cout << "false\n";
            } else {
                cout << "maybe\n";
            }
        }
        else {
            cout << "maybe\n";
        }
    }

    return 0;
}

复杂度

预处理 ST 表：

$O(n log n)$

每次询问：

二分找位置： $O(log n)$
ST 表查区间最大值： $O(1)$

总时间复杂度：

$O(n log n + m log n)$

空间复杂度：

$O(n log n)$

总结

这题最关键的不是 ST 表本身，而是先把原句翻译成：

两个端点的大小关系
中间区间最大值的限制
记录是否完整连续

一旦把这三个判断条件拆清楚，代码就只是“二分 + RMQ + 分类讨论”。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

代码

复杂度

总结

一图流解析