给定一个长度为 \(n\) 的序列，其中每个元素 \(i\) 由一个区间 \([x_i, y_i]\) 表示。任务是找到一个最长的连续子数组（区间），使得存在一个序列 \(v_1, v_2, \dots, v_k\)，其中 \(v_j \in [x_{start+j-1}, y_{start+j-1}]\) 对于子数组中的每个元素，且该序列 \(v\) 是非递减的（即 \(v_1 \le v_2 \le \dots \le v_k\)。

数据范围

• \(20\%\) 的数据：\(n \le 10\)
• \(40\%\) 的数据：\(n \le 3000\)
• \(50\%\) 的数据：\(n \le 10^5\)
• \(100\%\) 的数据：\(n \le 10^6\)

示例

输入

4
1 3
2 4
1 1
3 4
    

输出

2
    

暴力解法 (TLE)

对于 \(n \le 3000\) 的数据，可以尝试枚举所有可能的连续子数组的起始点，然后检查是否存在一个非递减序列。这种方法的时间复杂度为 \(O(n^3)\) 或 \(O(n^2)\)（如果检查优化），对于 \(n=3000\) 可能会超时。

复杂度分析

枚举子数组的起始点 \(i\) 和结束点 \(j\)，对于每个子数组 \([i, j]\)，检查是否存在非递减序列。最简单的检查方法是使用动态规划，时间复杂度为 \(O((j-i+1)^2)\)。总复杂度 \(O(n^4)\)。优化检查过程可以使用贪心或更快的 DP，将检查复杂度降至 \(O(j-i+1)\)，总复杂度 \(O(n^3)\)。即使是 \(O(n^2)\) 的方法，对于 \(n=10^6\) 也是不可行的。

示例暴力代码

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    int n;
    std::cin >> n;
    std::vector<int> lower_bound(n + 1);
    std::vector<int> upper_bound(n + 1);
    for (int i = 1; i <= n; ++i) {
        int x, y;
        std::cin >> x >> y;
        lower_bound[i] = std::min(x, y);
        upper_bound[i] = std::max(x, y);
    }

    int max_len = 0;
    for (int i = 1; i <= n; ++i) {
        int current_val = -1; // Sentinel value, assuming values are non-negative
        for (int j = i; j <= n; ++j) {
            // Check if we can extend the non-decreasing sequence
            if (current_val == -1 || lower_bound[j] >= current_val) {
                // If we can extend, update current_val to the minimum possible value for the next step
                current_val = std::max(current_val == -1 ? lower_bound[j] : current_val, lower_bound[j]);
                if (current_val <= upper_bound[j]) {
                    max_len = std::max(max_len, j - i + 1);
                } else {
                    // Cannot satisfy the condition for this j, break inner loop
                    break;
                }
            } else {
                // Cannot extend the non-decreasing sequence with lower_bound[j]
                break;
            }
        }
    }

    std::cout << max_len << std::endl;
    return 0;
}

优化解法 (单调队列)

这个问题可以通过维护一个单调队列来高效解决。我们遍历序列，对于每个元素 \(i\)，维护一个关于区间 \([x_i, y_i]\) 的信息。单调队列将帮助我们快速找到满足条件的区间。

维护一个单调队列 \(q\)，其中存储的是元素的索引。队列中的索引 \(k\) 满足 \([x_k, y_k]\) 的某个属性（例如 \(x_k\) 或 \(y_k\)）是递增的。

在处理元素 \(i\) 时，我们需要执行以下操作：

1. 移除无效区间： 如果队列首部的索引 \(q.front()\)，其对应的区间 \([x_{q.front()}, y_{q.front()}]\) 的上限 \(y_{q.front()}\) 小于当前元素 \(i\) 的下限 \(x_i\)，那么这个区间无法作为非递减序列的一部分，将其从队首移除。更进一步，如果队列首部的索引 \(k\) 对应的区间 \([x_k, y_k]\) 无法满足 \(v_{prev} \le x_k\)，即 \(y_{prev} < x_k\)，那么这个区间也需要被移除。我们维护一个变量 `invalid_start_idx` 来记录当前子数组中第一个无效元素的索引。
2. 更新队首： 如果队列首部的索引 \(k\) 对应的区间 \([x_k, y_k]\) 使得 \(x_k\) 小于 `invalid_start_idx` 所指向区间的 \(x\) 值，那么这个区间也需要被移除。
3. 维护单调性： 弹出队列尾部所有索引 \(k\) 使得 \(x_i \ge x_k\)。这是因为对于后续的元素，使用 \(i\) 替代 \(k\) 会提供一个更优（更大或相等）的下限，从而更容易延续非递减序列。
4. 加入当前元素： 将当前元素 \(i\) 的索引加入队列尾部。

在每次迭代中，当前最长有效子序列的长度可以通过 \(i - invalid\_start\_idx + 1\) 来计算，并更新全局最大长度。

优化代码实现

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    std::vector<int> lower_bound(n + 1);
    std::vector<int> upper_bound(n + 1);
    for (int i = 1; i <= n; ++i) {
        int x, y;
        std::cin >> x >> y;
        lower_bound[i] = std::min(x, y);
        upper_bound[i] = std::max(x, y);
    }

    std::deque<int> dq; // Stores indices
    int invalid_prefix_end_idx = 0; // Tracks the end index of the "invalid prefix" of the current potential subarray
    int max_len = 0;

    for (int i = 1; i <= n; ++i) {
        // Remove elements from the front of the deque whose upper bound is too small
        // to extend the sequence from the current invalid_prefix_end_idx
        while (!dq.empty() && upper_bound[dq.front()] < lower_bound[i]) {
             // This element dq.front() can no longer be part of a valid non-decreasing sequence starting from invalid_prefix_end_idx
            // So, the sequence must start after dq.front()
            invalid_prefix_end_idx = dq.front();
            dq.pop_front();
        }
        
        // Ensure the current element can start a valid sequence after the current invalid_prefix_end_idx
        // If the lower bound of the current element is less than the effective value at invalid_prefix_end_idx + 1,
        // we might need to advance invalid_prefix_end_idx.
        // This part is implicitly handled by the next loop.

        // Remove elements from the front that are now "dominated" or made invalid by invalid_prefix_end_idx
        while (!dq.empty() && dq.front() <= invalid_prefix_end_idx) {
            dq.pop_front();
        }

        // Maintain the increasing property of lower bounds in the deque
        // If the current element's lower bound is greater than or equal to the back element's lower bound,
        // the back element is suboptimal for extending sequences.
        while (!dq.empty() && lower_bound[i] >= lower_bound[dq.back()]) {
            dq.pop_back();
        }
        dq.push_back(i);

        // The longest valid sequence ending at i starts at invalid_prefix_end_idx + 1
        // and has length i - invalid_prefix_end_idx.
        max_len = std::max(max_len, i - invalid_prefix_end_idx);
    }

    std::cout << max_len << std::endl;

    return 0;
}

总结

这是一个经典的单调队列应用问题。通过维护一个存储索引的单调递增（基于区间下限）的双端队列，并配合一个指针追踪无效区间的起始点，可以在线性时间内找到最长的满足条件的连续子数组。

标签

提高+/省选−, 动态规划, DP, 单调队列, 队列, POI (波兰), 2011