寻找中位数 plus - 题解

标签与难度

标签: 数据结构, 线段树, 中位数, 问题简化, 区间查询, 单点修改 难度: 2100

题目大意喵~

主人你好呀~！这道题目是这样的：我们有一个长度为 $n$ 的正整数数组 $a$ 和一个特殊的正整数 $k$。接下来会有 $q$ 次操作，操作有两种：

1. 1 i x: 把数组 $a$ 的第 $i$ 个位置的数字改成 $x$。
2. 2 l r: 问你呀，在数组 $a$ 的区间 $[l, r]$ 里面，存不存在一个连续的子数组，它的长度至少是 2，并且它的中位数正好是 $k$ 呢？

中位数的定义是：把一个长度为 $m$ 的数组排好序后，排在第 $\lfloor \frac{m+1}{2} \rfloor$ 位置的那个数就是中位数啦，喵~

解题思路分析

这道题看起来有点吓人呢，又是中位数，又是区间查询，又是修改，一大堆东西缠在一起，就像一团乱糟糟的毛线球，喵~ 但是别怕，让我来帮你一点点解开它！

步骤一：转化中位数条件

直接处理中位数是非常麻烦的，因为它需要排序。对于动态变化的区间，我们不可能每次都暴力排序。所以，第一步就是要把“中位数是 $k$”这个条件，转化成一个更容易处理的形式。

一个子数组的中位数是 $k$，需要满足两个条件：

1. 这个子数组里必须有数字 $k$。
2. 当数组排好序后，数字 $k$ 恰好在中间位置。

这个“中间位置”的条件还是有点模糊。我们来换个角度思考！我们只关心数组里的数和 $k$ 的大小关系。

• 如果一个数大于等于 $k$，我们叫它“大朋友”。
• 如果一个数小于 $k$，我们叫它“小朋友”。

一个数组的中位数如果大于等于 $k$，那说明把它排好序后，中间那个位置以及后面的数都是“大朋友”。这意味着，“大朋友”的数量必须严格多于“小朋友”的数量。比如 [1, 5, 6, 7]，k=5，大朋友有 {5,6,7} (3个)，小朋友有 {1} (1个)，$3 > 1$，所以中位数是 6，确实 >=k。

那么，中位数正好是 $k$ 呢？ 一个聪明的想法是，如果我们能找到一个子数组，它满足一个更简单的、但足够强的条件，就能保证答案是 "YES"，那问题就简单多啦！

这里有一个非常关键的结论，喵~ (需要一点点证明，但我们可以先相信它)： 如果区间 $[l, r]$ 内存在任何一个长度不小于2、包含数字 $k$、且其中“大朋友”（$\ge k$ 的数）数量严格大于“小朋友”（$< k$ 的数）数量的连续子数组，那么答案就是 "YES"。

为什么这个结论是对的呀？(可选的深入思考) 假设我们找到了这样一个子数组。如果它本身的中位数就是 $k$，那太好啦！如果不是，比如是 [10, 11, 12, 5, 1]，k=5，这个数组满足条件，但中位数是 10。 但是！我们可以看看它的子数组。比如 [12, 5]，它也满足条件（2个大朋友，0个小朋友），并且它的中位数就是 5！ 我们可以证明，任何一个满足上述条件的子数组，我们总能通过裁剪它的两端（去掉那些让中位数偏离 $k$ 的元素），最终得到一个更短的、中位数恰好为 $k$ 的子数组。所以，我们只需要检查那个简化的条件就够了！

步骤二：把问题数值化

现在问题变成了：寻找一个子数组 [i, j]，它在查询范围 [l, r] 内，长度至少为 2，包含 k，并且 count(x >= k) > count(x < k)。

这个大小比较还是不方便，我们把它变成加法！

• 如果 a[p] >= k，我们记作 b[p] = 1。
• 如果 a[p] < k，我们记作 b[p] = -1。

那么 count(x >= k) - count(x < k) 就等于子数组 b[i..j] 的和 sum(b[i..j])！ 条件 count(x >= k) > count(x < k) 就变成了 sum(b[i..j]) > 0。因为和是整数，所以等价于 sum(b[i..j]) >= 1。

好耶！我们的任务现在是： 在区间 [l, r] 内，是否存在一个长度不小于2的连续子数组 [i, j]，它包含至少一个 k，并且其对应的 b 数组的和大于等于 1？

步骤三：线段树出击！

这个问题有单点修改和区间查询，是线段树的拿手好戏！我们需要设计一个线段树的节点，它能存储足够的信息，让我们快速地合并区间。

对于线段树的每个节点，我们维护以下信息：

1. exists: 一个布尔值，表示当前节点代表的区间内，是否已经找到了一个满足条件的子数组。
2. sum: 区间内 b 数组的总和。
3. max_pref: 区间内 b 数组的最大前缀和。
4. max_suff: 区间内 b 数组的最大后缀和。
5. max_pref_k: 区间内，包含 k 的最大前缀和。
6. max_suff_k: 区间内，包含 k 的最大后缀和。

喵？最后两个看起来好怪哦。特别是，我们怎么知道一个前缀/后缀是否包含 k 呢？ 这里有一个小小的魔法！我们不直接存 sum，而是存 sum - 1。

• max_pref_k: 存储 (包含k的最大前缀和) - 1。如果不存在含 k 的前缀，就存一个非常小的负数（负无穷）。
• max_suff_k: 存储 (包含k的最大后缀和) - 1。

为什么是 sum - 1 呢？ 因为我们想要的条件是 sum >= 1。把它变成 sum - 1 >= 0，在处理时会更方便，特别是处理跨区间的合并时。

节点初始化 (叶子节点): 对于数组中的一个位置 p，它的值是 a[p]：

• b[p] 的值是 (a[p] >= k ? 1 : -1)。
• exists = false (因为长度为1，不满足 >=2)。
• sum = max_pref = max_suff = b[p]。
• 如果 a[p] == k:
  • max_pref_k = b[p] - 1 = 1 - 1 = 0。
  • max_suff_k = b[p] - 1 = 1 - 1 = 0。
• 如果 a[p] != k:
  • max_pref_k = -INF。
  • max_suff_k = -INF。

节点合并 (pushup): 假设我们要合并左孩子 L 和右孩子 R 到父节点 P。

• P.sum, P.max_pref, P.max_suff 是经典的最大子段和合并方式。
• P.exists = L.exists || R.exists。
• P.max_pref_k = max(L.max_pref_k, L.sum + R.max_pref_k)。
• P.max_suff_k = max(R.max_suff_k, R.sum + L.max_suff_k)。
• 最关键的一步：检查跨越中心的新子数组。一个跨中心的子数组由 L 的一个后缀和 R 的一个前缀组成。
  • 如果 L 的后缀提供了 k：子数组和是 L.max_suff_k + 1 + R.max_pref。我们要检查 sum >= 1，即 L.max_suff_k + 1 + R.max_pref >= 1，化简得 L.max_suff_k + R.max_pref >= 0。
  • 如果 R 的前缀提供了 k：同理，检查 L.max_suff + R.max_pref_k >= 0。
  • 如果这两个条件任意一个成立，就说明我们找到了一个跨中心的有效子数组，P.exists 设为 true。

这样，我们就可以用线段树在 $O(\log N)$ 的时间里完成修改和查询啦！对于每个查询 [l, r]，我们在线段树上找到对应的若干个节点，把它们的信息合并起来，最后检查总的 exists 标志位就可以啦！

代码实现

这是我根据上面的思路，精心重构的一份代码哦~ 注释超详细的，希望能帮到你，喵！

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

using namespace std;

const int INF = 1e9; // 用一个大数表示负无穷

int N, K, Q;
vector<int> a;

// 线段树节点结构体，喵~
struct Node {
    bool exists;             // 是否存在满足条件的子数组
    int sum;                 // 区间和 (>=k为1, <k为-1)
    int max_pref;            // 最大前缀和
    int max_suff;            // 最大后缀和
    int max_pref_k;          // (含k的最大前缀和) - 1
    int max_suff_k;          // (含k的最大后缀和) - 1
};

vector<Node> tree;

// 合并两个节点的函数，这是线段树的核心魔法！
Node merge(const Node& left, const Node& right) {
    Node res;
    
    // 1. 合并基础信息
    res.sum = left.sum + right.sum;
    res.max_pref = max(left.max_pref, left.sum + right.max_pref);
    res.max_suff = max(right.max_suff, right.sum + left.max_suff);
    
    // 2. 合并含k的前/后缀和信息
    res.max_pref_k = max(left.max_pref_k, left.sum + right.max_pref_k);
    res.max_suff_k = max(right.max_suff_k, right.sum + left.max_suff_k);
    
    // 3. 计算是否存在满足条件的子数组
    res.exists = left.exists || right.exists;
    
    // 检查跨越中心的子数组
    // Case 1: k在左半边的后缀 + 右半边的前缀
    if (left.max_suff_k != -INF && right.max_pref != -INF) {
        if (left.max_suff_k + right.max_pref >= 0) {
            res.exists = true;
        }
    }
    // Case 2: 左半边的后缀 + k在右半边的前缀
    if (left.max_suff != -INF && right.max_pref_k != -INF) {
        if (left.max_suff + right.max_pref_k >= 0) {
            res.exists = true;
        }
    }
    
    return res;
}

// 根据单个元素的值创建叶子节点
Node make_leaf(int val) {
    Node leaf;
    int b_val = (val >= K) ? 1 : -1;
    leaf.exists = false; // 单个元素长度不足2
    leaf.sum = b_val;
    leaf.max_pref = b_val;
    leaf.max_suff = b_val;
    if (val == K) {
        leaf.max_pref_k = b_val - 1; // 1 - 1 = 0
        leaf.max_suff_k = b_val - 1; // 1 - 1 = 0
    } else {
        leaf.max_pref_k = -INF;
        leaf.max_suff_k = -INF;
    }
    return leaf;
}

// 构建线段树
void build(int node_idx, int l, int r) {
    if (l == r) {
        tree[node_idx] = make_leaf(a[l]);
        return;
    }
    int mid = l + (r - l) / 2;
    build(2 * node_idx, l, mid);
    build(2 * node_idx + 1, mid + 1, r);
    tree[node_idx] = merge(tree[2 * node_idx], tree[2 * node_idx + 1]);
}

// 单点修改
void update(int node_idx, int l, int r, int pos, int new_val) {
    if (l == r) {
        tree[node_idx] = make_leaf(new_val);
        return;
    }
    int mid = l + (r - l) / 2;
    if (pos <= mid) {
        update(2 * node_idx, l, mid, pos, new_val);
    } else {
        update(2 * node_idx + 1, mid + 1, r, pos, new_val);
    }
    tree[node_idx] = merge(tree[2 * node_idx], tree[2 * node_idx + 1]);
}

// 区间查询
Node query(int node_idx, int l, int r, int query_l, int query_r) {
    if (query_l <= l && r <= query_r) {
        return tree[node_idx];
    }
    int mid = l + (r - l) / 2;
    bool left_in = (query_l <= mid);
    bool right_in = (query_r > mid);

    if (left_in && right_in) {
        return merge(query(2 * node_idx, l, mid, query_l, query_r),
                     query(2 * node_idx + 1, mid + 1, r, query_l, query_r));
    }
    if (left_in) {
        return query(2 * node_idx, l, mid, query_l, query_r);
    }
    // if (right_in)
    return query(2 * node_idx + 1, mid + 1, r, query_l, query_r);
}

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

    cin >> N >> K >> Q;
    a.resize(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> a[i];
    }

    tree.resize(4 * N + 4);
    build(1, 1, N);

    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int i, x;
            cin >> i >> x;
            update(1, 1, N, i, x);
        } else {
            int l, r;
            cin >> l >> r;
            if (l > r) { // Just in case
                 cout << "NO\n";
                 continue;
            }
            Node result = query(1, 1, N, l, r);
            if (result.exists) {
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        }
    }

    return 0;
}

复杂度分析

• 时间复杂度: $O(N + Q \log N)$

  • build 函数构建整个线段树需要 $O(N)$ 的时间。
  • 每次 update 或 query 操作都需要从根节点走到叶子节点，或者遍历部分树，路径长度都是 $O(\log N)$。总共有 $Q$ 次操作，所以这部分是 $O(Q \log N)$。
  • 合并两个节点信息是常数时间的操作，所以总时间复杂度是 $O(N + Q \log N)$，非常高效哦！

• 空间复杂度: $O(N)$

  • 我们需要一个数组 a 来存原始数据，大小为 $O(N)$。
  • 线段树本身需要大约 $4N$ 个节点来存储信息，所以空间复杂度是 $O(N)$。

知识点总结

这道题是检验综合能力的好题目呢，喵~ 它涉及到了：

1. 问题转化: 核心技巧！将复杂、不直观的“中位数”条件，转化为一个等价的、更简单的数值条件（子数组和大于0）。这是解题的关键突破口。
2. 线段树: 解决动态区间问题的强大工具。这道题的难点在于设计线段树节点需要维护的状态，以及如何正确地合并这些状态。
3. 最大子段和思想: 我们维护的 max_pref, max_suff 等信息，都是经典最大子段和问题的变种和延伸。
4. 细节处理: 比如长度至少为2的约束，通过在叶子节点将 exists 设为 false，只在合并（长度必然大于1）时才可能变为 true，巧妙地解决了。还有用 sum-1 来简化判断条件 sum >= 1 为 sum' >= 0 的小技巧。

希望这篇题解能帮到你！继续加油，你超棒的，喵~！