Find the median - 题解

标签与难度

标签: 数据结构, 线段树, 离散化, 懒惰标记, 动态中位数, 坐标压缩难度: 2200

题目大意喵~

你好呀，未来的算法大师！本喵今天带来了一道非常有趣的题目哦~

是这样的，我们一开始有一个空空如也的数列。接下来会有 N 次操作。每一次操作，题目会给我们两个数字 $L_i$ 和 $R_i$ ，然后我们要把从 $\min(L_i, R_i)$ 到 $\max(L_i, R_i)$ 的所有整数（包括两端哦！）都加入到我们的数列里。

在每次操作之后，我们都需要找到当前数列的中位数，然后把它打印出来。

中位数的定义是：如果把数列排序，排在最中间的那个数就是中位数。如果数列的长度是偶数，那就有两个中间数，我们取其中较小的那一个。举个例子：

对于 [10, 3, 2, 3, 2]，排序后是 [2, 2, 3, 3, 10]，长度是 5，中间的第 3 个数是 3，所以中位数是 3。
对于 [1, 5, 8, 1]，排序后是 [1, 1, 5, 8]，长度是 4，中间两个数是 1 和 5，较小的是 1，所以中位数是 1。

一个方便的小技巧是，对于一个长度为 $M$ 的已排序数列，中位数总是第 $\lfloor \frac{M+1}{2} \rfloor$ 个元素（1-based index），喵~

解题思路分析

这道题如果直接模拟，会非常非常慢的说！你想呀，每次操作可能加入超多数，数列会变得超级长，每次都排序的话，本喵的爪子都要磨秃啦！ $N$ 最大有 $10^5$ ，数值可以到 $10^9$ ，直接存下来是绝对不行的。所以，我们需要更聪明的办法，喵！

步骤一：从具体数值到区间计数

我们首先要意识到，我们并不真的关心每一个被加入的数字本身，而是关心有多少个数字被加入了。而且，每次加入的都是一个连续的整数区间。这就给了我们一个重要的提示：问题的关键在于如何高效地处理这些区间的叠加和查询。

数值的范围很大（高达 $10^9$ ），但是操作次数 $N$ 只有 $10^5$ 。这意味着，所有操作涉及到的区间端点最多只有 $2N$ 个。这些端点才是真正“重要”的位置！它们把整个数轴划分成了一系列基本区间。在任何一个这样的基本区间内部，所有数字的行为都是完全一致的——要么它们都被某个操作覆盖，要么都没被覆盖。

步骤二：坐标离散化 (Coordinate Discretization)

这就是离散化大显身手的时候啦！我们可以把所有操作的端点 $L_i$ 和 $R_i+1$ （用 $R_i+1$ 是为了方便表示左闭右开区间 [L, R+1)) 收集起来，然后排序并去重。这样我们就得到了一系列关键坐标点 $p_1, p_2, \dots, p_m$ 。

这些点将数轴分成了 $m-1$ 个基本区间： $[p_1, p_2-1], [p_2, p_3-1], \dots, [p_{m-1}, p_m-1]$ 。现在，我们就不需要关心 $10^9$ 那么大的范围了，只需要关心这 $m-1$ 个基本区间就好啦！

步骤三：请出线段树！

对于这种在区间上进行修改和查询的问题，线段树是我们的好朋友，喵~

我们可以建立一棵线段树，它的叶子节点就对应着我们离散化后的 $m-1$ 个基本区间。

线段树的每个节点需要维护一些信息：
1. element_count (或 sum)：表示这个节点所代表的区间范围内，当前总共有多少个数字。
2. lazy_add：懒惰标记！表示这个节点所代表的区间范围，被操作“完整覆盖”了多少次。

步骤四：处理操作

更新操作 (Update): 当我们要加入区间 $[L, R]$ 的所有数字时：

首先，在离散化的坐标点中找到 $L$ 和 $R+1$ 对应的下标 l_idx 和 r_idx。
然后，我们在线段树上对下标范围 [l_idx, r_idx - 1] 进行一次区间更新。
对于被完整覆盖的线段树节点，我们给它的 lazy_add 加 1。同时，它的 element_count 也要增加。增加多少呢？就是这个节点代表的总区间长度。例如，如果一个节点被覆盖了，它代表的区间是 $[p_j, p_k-1]$ ，那么它的 element_count 就增加 $p_k - p_j$ 。
通过懒惰标记的下推（push_down），我们可以高效地完成更新。当一个节点的 lazy_add 标记要下推给子节点时，子节点的 lazy_add 继承父节点的标记，并且子节点的 element_count 也要相应地增加 parent.lazy_add * (子节点代表的区间总长度)。

查询操作 (Query): 这是最有趣的部分！每次更新后，我们需要找到中位数。

首先，整个数列的总元素个数就是线段树根节点的 element_count，我们记为 total_elements。
根据中位数的定义，我们要找的是第 $k = \lfloor \frac{\text{total\_elements}+1}{2} \rfloor$ 小的数。
我们可以在线段树上进行二分查找来定位这个第 $k$ $k$ 小的数！
- 从根节点开始，目标是找到第 $k$ 个数。
- 在当前节点，我们先 push_down 懒惰标记，确保子节点信息是正确的。
- 查看左子节点的 element_count。
- 如果 $k \le \text{left\_child.element\_count}$ ，说明我们要找的数在左子节点代表的区间里，于是我们递归到左子节点，继续寻找第 $k$ 小的数。
- 如果 $k > \text{left\_child.element\_count}$ ，说明第 $k$ 小的数在右子节点代表的区间里。我们递归到右子节点，但是要找的就不是第 $k$ 小了，而是第 $(k - \text{left\_child.element\_count})$ 小的数。
这个过程最终会到达一个叶子节点。这个叶子节点代表一个基本区间 $[p_j, p_{j+1}-1]$ 。此时我们知道，中位数就在这个区间里！
假设到达这个叶子节点时，我们的目标是寻找它内部的第 $k'$ 小的数。这个叶子节点被操作覆盖的总次数（也就是它累积的 lazy_add 值），我们称之为 coverage_count。这意味着在这个基本区间里，每个数（从 $p_j$ 到 $p_{j+1}-1$ ）都重复了 coverage_count 次。
那么，第 $k'$ 小的数就是 $p_j + \lfloor \frac{k'-1}{\text{coverage\_count}} \rfloor$ 。想一想，是不是很奇妙？我们把 $k'$ 个元素分成 coverage_count 个一组，看看它落在哪一组里。

这样，我们就能在每次操作后，高效地找到中位数啦！喵~

代码实现

这是本喵根据上面的思路，精心重构的一份代码，希望能帮助你理解，喵~

cpp

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

using namespace std;

// 使用 long long 防止计算过程中溢出
using ll = long long;

// 线段树节点结构体
struct Node {
    ll element_count; // 该节点覆盖的区间内总共有多少个元素
    ll lazy_add;      // 懒惰标记，表示该区间被完整添加了多少次
};

// 全局变量
vector<ll> X, Y;
ll A1, B1, C1, M1;
ll A2, B2, C2, M2;
vector<int> discretized_points; // 存储所有离散化后的坐标点
vector<Node> seg_tree;

// 生成 L_i 和 R_i 的函数
void generate_next(int i) {
    X[i] = (A1 * X[i - 1] + B1 * X[i - 2] + C1) % M1;
    Y[i] = (A2 * Y[i - 1] + B2 * Y[i - 2] + C2) % M2;
}

// 线段树的 push_down 操作，将父节点的懒惰标记下传给子节点
void push_down(int node_idx, int l, int r) {
    if (seg_tree[node_idx].lazy_add == 0 || l == r) {
        return;
    }

    int mid = l + (r - l) / 2;
    int left_child = 2 * node_idx;
    int right_child = 2 * node_idx + 1;
    ll lazy_val = seg_tree[node_idx].lazy_add;

    // 更新左子节点
    seg_tree[left_child].lazy_add += lazy_val;
    ll left_interval_len = discretized_points[mid + 1] - discretized_points[l];
    seg_tree[left_child].element_count += lazy_val * left_interval_len;

    // 更新右子节点
    seg_tree[right_child].lazy_add += lazy_val;
    ll right_interval_len = discretized_points[r + 1] - discretized_points[mid + 1];
    seg_tree[right_child].element_count += lazy_val * right_interval_len;
    
    // 清除父节点的懒惰标记
    seg_tree[node_idx].lazy_add = 0;
}

// 线段树的区间更新
void update(int node_idx, int l, int r, int update_l, int update_r) {
    if (update_l <= l && r <= update_r) {
        seg_tree[node_idx].lazy_add++;
        ll interval_len = discretized_points[r + 1] - discretized_points[l];
        seg_tree[node_idx].element_count += interval_len;
        return;
    }

    push_down(node_idx, l, r);

    int mid = l + (r - l) / 2;
    if (update_l <= mid) {
        update(2 * node_idx, l, mid, update_l, update_r);
    }
    if (update_r > mid) {
        update(2 * node_idx + 1, mid + 1, r, update_l, update_r);
    }

    seg_tree[node_idx].element_count = seg_tree[2 * node_idx].element_count + seg_tree[2 * node_idx + 1].element_count;
}

// 在线段树上查询第 k 小的元素
ll query_kth_element(int node_idx, int l, int r, ll k) {
    if (l == r) { // 到达叶子节点
        // 叶子节点代表的区间是 [discretized_points[l], discretized_points[l+1] - 1]
        // 这个区间被覆盖了 lazy_add 次
        // 我们要找这个区间里的第 k 小的数
        return discretized_points[l] + (k - 1) / seg_tree[node_idx].lazy_add;
    }

    push_down(node_idx, l, r);

    int mid = l + (r - l) / 2;
    int left_child = 2 * node_idx;
    
    if (k <= seg_tree[left_child].element_count) {
        return query_kth_element(left_child, l, mid, k);
    } else {
        return query_kth_element(2 * node_idx + 1, mid + 1, r, k - seg_tree[left_child].element_count);
    }
}


int main() {
    // 加速输入输出，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    X.resize(n + 1);
    Y.resize(n + 1);
    vector<pair<int, int>> ranges(n);
    vector<int> temp_points;

    cin >> X[1] >> X[2] >> A1 >> B1 >> C1 >> M1;
    cin >> Y[1] >> Y[2] >> A2 >> B2 >> C2 >> M2;
    
    // 生成所有 L_i, R_i 并收集端点
    for (int i = 1; i <= n; ++i) {
        if (i > 2) {
            generate_next(i);
        }
        ll Li = min(X[i], Y[i]) + 1;
        ll Ri = max(X[i], Y[i]) + 1;
        ranges[i - 1] = { (int)Li, (int)Ri };
        temp_points.push_back(Li);
        temp_points.push_back(Ri + 1); // 使用 [L, R+1) 左闭右开区间
    }
    
    // 坐标离散化
    sort(temp_points.begin(), temp_points.end());
    temp_points.erase(unique(temp_points.begin(), temp_points.end()), temp_points.end());
    discretized_points = temp_points;
    
    int m = discretized_points.size();
    seg_tree.resize(4 * m, {0, 0});

    ll total_elements = 0;
    for (const auto& range : ranges) {
        ll l_val = range.first;
        ll r_val = range.second;
        total_elements += (r_val - l_val + 1);

        // 找到 L 和 R+1 在离散化数组中的下标
        auto it_l = lower_bound(discretized_points.begin(), discretized_points.end(), l_val);
        auto it_r = lower_bound(discretized_points.begin(), discretized_points.end(), r_val + 1);
        int l_idx = distance(discretized_points.begin(), it_l);
        int r_idx = distance(discretized_points.begin(), it_r);

        // 在线段树上更新 [l_idx, r_idx-1]
        if (l_idx < r_idx) {
            update(1, 0, m - 2, l_idx, r_idx - 1);
        }
        
        // 找到中位数的位置 k
        ll k = (total_elements + 1) / 2;
        
        // 查询第 k 小的元素并输出
        cout << query_kth_element(1, 0, m - 2, k) << "\n";
    }

    return 0;
}

复杂度分析

时间复杂度: $O(N \log N)$
- 首先，我们需要生成 $N$ 个区间，这需要 $O(N)$ 的时间。
- 收集所有 $2N$ 个端点并进行排序去重（离散化），需要 $O(N \log N)$ 的时间。
- 之后，我们进行 $N$ $N$ 次操作。每次操作包括：
  1. 两次 lower_bound 在离散化坐标上查找，耗时 $O(\log N)$ 。
  2. 一次线段树的区间更新，树的大小是 $O(N)$ ，所以耗时 $O(\log N)$ 。
  3. 一次线段树的单点查询（查找第k小元素），耗时 $O(\log N)$ 。
- 所以总的时间复杂度是 $O(N \log N)$ ，非常高效的说！
空间复杂度: $O(N)$
- 我们需要存储 $N$ 个区间的端点信息，以及离散化后的坐标点，这都是 $O(N)$ 的空间。
- 线段树的大小是离散化后坐标点数量的4倍左右，也就是 $O(m)$ ，其中 $m \le 2N$ ，所以空间复杂度也是 $O(N)$ 。

知识点总结

这道题是多种算法思想的美妙结合，学到就是赚到哦，喵~

问题转化: 核心是把对具体数值的操作，转化为对数值区间和计数的操作。
坐标离散化: 当数值范围巨大，但关键操作点数量有限时，离散化是降维打击的神器！它能大大缩小我们需要处理的数据规模。
线段树与懒惰标记: 线段树是处理区间问题的万能工具。对于区间修改，懒惰标记可以把时间复杂度从线性降到对数级别。
在数据结构上二分: 本题的查询不是简单的求和或最值，而是“查找第k小元素”。这种查询可以通过在树形数据结构（如线段树、平衡树）上进行二分查找来高效完成，利用了每个子树中元素的数量信息来决定搜索方向。

希望这篇题解能帮到你！如果还有不明白的地方，随时可以再来问本喵哦~ 加油，你超棒的！喵~

Find the median - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

步骤一：从具体数值到区间计数 ​

步骤二：坐标离散化 (Coordinate Discretization) ​

步骤三：请出线段树！ ​

步骤四：处理操作 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​