[POI 2011] TEM-Temperature

题意

第 i 天的真实温度 t_i 不知道，但一定落在区间：

x_i <= t_i <= y_i

题目要求找出一段最长的连续区间 [l,r]，使得可以为这几天各选一个真实温度，满足：

t_l <= t_{l+1} <= ... <= t_r

也就是这段时间的温度可能一直没有下降。

思路

先看一个最直接的暴力程序：

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5005;

int n;
int x_arr[MAXN], y_arr[MAXN];

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

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

    int ans = 1;
    for (int l = 1; l <= n; l++) {
        int max_low = x_arr[l];
        for (int r = l; r <= n; r++) {
            max_low = max(max_low, x_arr[r]);
            if (max_low <= y_arr[r]) {
                ans = max(ans, r - l + 1);
            }
            else {
                break;
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

暴力做法枚举左端点 l，不断扩展右端点 r，并维护区间中的 x 最大值。
如果出现：

max(x_l...x_r) > y_r

就说明区间不可能继续合法了。

这个做法容易理解，但最坏复杂度是 $O(n^2)$ 。

最关键的等价转化

区间 [l,r] 合法，当且仅当不存在一对 i<j 满足：

x_i > y_j

为什么？

如果 x_i > y_j，那么第 i 天真实温度至少是 x_i，第 j 天真实温度至多是 y_j，于是一定有 t_i > t_j，不可能不下降；
反过来，如果所有前后位置都满足 x_i <= y_j，就不会出现这种硬冲突，区间可以构造出一个不下降温度序列。

所以整题变成：

最长连续区间中，不能包含任意一组冲突对 (i,j)。

先求每个位置的第一个冲突点

定义：

bad_pos[i] = 最小的 j>i，满足 y_j < x_i

也就是第 i 天第一次和右边哪一天产生冲突。

如果不存在这样的 j，就记成无穷大。

那么区间 [l,r] 合法，当且仅当：

对区间内所有 i，都有 bad_pos[i] > r

也就是：

min(bad_pos[l..r]) > r

怎么高效求 bad_pos

从右往左扫描。

处理到 i 时，右侧所有 y_j 都已经加入数据结构。
我们想找的是：

所有 y_j < x_i 的位置中，最小的 j

把所有 y 做坐标压缩后，可以用树状数组维护：

某个值域前缀里出现过的最小下标

于是：

查询前缀 < x_i 的最小下标，就是 bad_pos[i]
再把当前 y_i 对应的位置插入树状数组

每次操作都是 $O(log n)$ 。

最长合法区间怎么求

现在我们已经有了数组 bad_pos。

问题就变成：

找最长区间 [l,r]
使得 min(bad_pos[l..r]) > r

这就是一个滑动窗口问题。

用双指针枚举右端点 r，再用单调队列维护窗口内最小 bad_pos：

如果当前最小 bad_pos > r，窗口合法，可以继续扩展；
如果最小 bad_pos <= r，说明冲突已经落进窗口，需要不断右移左端点，直到窗口重新合法。

代码

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;
const int INF = 0x3f3f3f3f;

int n;
int x_arr[MAXN], y_arr[MAXN];
int all_y[MAXN];
int bit_min_pos[MAXN];
int bad_pos[MAXN];

// 树状数组维护前缀最小值。
void update(int idx, int val, int size) {
    while (idx <= size) {
        bit_min_pos[idx] = min(bit_min_pos[idx], val);
        idx += idx & -idx;
    }
}

int query(int idx) {
    int res = INF;
    while (idx > 0) {
        res = min(res, bit_min_pos[idx]);
        idx -= idx & -idx;
    }
    return res;
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x_arr[i] >> y_arr[i];
        all_y[i] = y_arr[i];
    }

    sort(all_y + 1, all_y + n + 1);
    int m = (int)(unique(all_y + 1, all_y + n + 1) - (all_y + 1));

    for (int i = 1; i <= m; i++) {
        bit_min_pos[i] = INF;
    }

    // bad_pos[i] 表示最靠左的一个 j>i，使得 y_j < x_i。
    // 一旦这样的 j 落进区间 [l,r]，那么第 i 天与第 j 天就无法同时属于同一个不下降区间。
    for (int i = n; i >= 1; i--) {
        int pos_x = (int)(lower_bound(all_y + 1, all_y + m + 1, x_arr[i]) - all_y);
        if (pos_x > 1) {
            bad_pos[i] = query(pos_x - 1);
        }
        else {
            bad_pos[i] = INF;
        }

        int pos_y = (int)(lower_bound(all_y + 1, all_y + m + 1, y_arr[i]) - all_y);
        update(pos_y, i, m);
    }

    deque<int> q;
    int ans = 1;
    int l = 1;

    for (int r = 1; r <= n; r++) {
        // 队列维护当前窗口内 bad_pos 的最小值。
        while (!q.empty() && bad_pos[q.back()] >= bad_pos[r]) {
            q.pop_back();
        }
        q.push_back(r);

        while (!q.empty() && q.front() < l) {
            q.pop_front();
        }

        // 如果窗口里有人的 bad_pos 已经落进了当前 r，
        // 说明窗口内已经出现冲突，只能把左端点右移。
        while (!q.empty() && bad_pos[q.front()] <= r) {
            l = q.front() + 1;
            q.pop_front();
            while (!q.empty() && q.front() < l) {
                q.pop_front();
            }
        }

        ans = max(ans, r - l + 1);
    }

    cout << ans << '\n';
    return 0;
}

复杂度

时间复杂度： $O(n log n)$
其中树状数组和坐标压缩是 $O(n log n)$ ，双指针部分是 $O(n)$ 。
空间复杂度： $O(n)$

总结

这题最难的地方，不在实现，而在于先看出：

合法区间的本质是“不能有前面的下界大于后面的上界”
这可以转成每个位置的第一个冲突点 bad_pos
再把原问题压成一个标准的最长合法滑动窗口

这一步转化完成后，后面的数据结构只是自然落实。

一图流解析

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