「COCI 2023.2」Vrsta 题解

题目大意

动态维护一个多重集合，支持批量插入操作。每次插入 $a_i$ 个值为 $v_i$ 的元素后，需要查询当前集合的中位数（如果元素个数为偶数，取中间两个元素中较小的那个）。

解题思路

核心算法：权值线段树

使用权值线段树来维护所有身高值的出现次数，通过线段树的区间和性质快速找到第 $k$ 小的元素。

算法步骤

1. 离散化处理

std::vector<int> v(n), a(n), o(n);
for (int i = 0; i < n; ++i) {
    scanf("%d%d", &v[i], &a[i]);
    o[i] = v[i];  // 收集所有出现的身高值
}

std::sort(o.begin(), o.end());
o.erase(std::unique(o.begin(), o.end()), o.end());

• 由于 $v_i$ 的范围很大（最大 $10^9$），但不同的 $v_i$ 最多只有 $n$ 个
• 将身高值映射到 $[0, n-1]$ 的范围内

2. 权值线段树设计

class segment_tree_t {
    std::vector<int64_t> sum;  // 维护区间内元素个数的和
public:
    void modify(int x, int l, int r, int p, int v) {
        sum[x] += v;  // 更新区间和
        // 递归更新子区间
    }
    int query(int x, int l, int r, int64_t k) {
        // 查询第k小的元素位置
        if (l == r) return l;
        int mid = (l + r) >> 1;
        if (k <= sum[x << 1])  // 第k小在左子树
            return query(x << 1, l, mid, k);
        else  // 第k小在右子树
            return query(x << 1 | 1, mid + 1, r, k - sum[x << 1]);
    }
};

3. 中位数计算

int64_t sum_a = 0;  // 当前总人数
for (int i = 0; i < n; ++i) {
    int p = std::lower_bound(o.begin(), o.end(), v[i]) - o.begin();
    tree.modify(1, 0, o.size() - 1, p, a[i]);  // 插入a[i]个v[i]
    sum_a += a[i];
    
    // 计算中位数位置：(总人数 + 1) / 2
    int median_pos = (sum_a + 1) >> 1;
    printf("%d\n", o[tree.query(1, 0, o.size() - 1, median_pos)]);
}

关键点解释

中位数位置计算

• 总人数为奇数：中位数位置 = $(总数 + 1) / 2$
• 总人数为偶数：中位数位置 = $总数 / 2$（取较矮的那个）
• 两种情况可以统一为：(sum_a + 1) >> 1

例子：

• 总数 = 5：位置 = (5+1)/2 = 3
• 总数 = 4：位置 = (4+1)/2 = 2（取第2个，即两个中间值中较矮的）

线段树查询原理

线段树每个节点维护区间内元素的总个数，查询第 $k$ 小元素时：

1. 如果左子树的元素个数 $\geq k$，则第 $k$ 小在左子树
2. 否则在右子树中找第 $(k - 左子树元素个数)$ 小的元素

复杂度分析

• 离散化：$O(n \log n)$
• 每次插入：$O(\log n)$
• 每次查询中位数：$O(\log n)$
• 总复杂度：$O(n \log n)$

样例分析

样例1：

输入：    离散化后：o = [1,2,3]
操作：
v=2,a=1: 插入1个2，总数=1，中位数位置=1 → 查询第1小=2
v=3,a=1: 插入1个3，总数=2，中位数位置=1 → 查询第1小=2  
v=1,a=1: 插入1个1，总数=3，中位数位置=2 → 查询第2小=2
输出：2,2,2

样例2：

离散化后：o = [9,11,17,23]

操作1: v=17,a=2
  线段树：位置2(17)计数+2，总数=2
  中位数位置=(2+1)/2=1 → 第1小=17

操作2: v=23,a=5  
  线段树：位置3(23)计数+5，总数=7
  中位数位置=(7+1)/2=4 → 第4小=23

操作3: v=11,a=4
  线段树：位置1(11)计数+4，总数=11  
  中位数位置=(11+1)/2=6 → 第6小=17

操作4: v=9,a=5
  线段树：位置0(9)计数+5，总数=16
  中位数位置=(16+1)/2=8 → 第8小=11

代码优势

1. 简洁高效：使用递归线段树实现，代码清晰
2. 离散化优化：处理大值域问题
3. 统一处理：奇偶情况统一计算公式
4. 在线处理：逐个处理输入，无需存储所有数据

总结

本题展示了权值线段树在动态顺序统计问题中的经典应用。通过维护元素个数的区间和，可以高效支持：

• 批量插入
• 第 $k$ 小查询
• 动态中位数维护

这种解法适用于需要频繁查询顺序统计量的场景，是处理此类问题的标准方法。