Order Statistics 题解

一、题目回顾（精简版）

给定数组 $a_1,\dots,a_n$，对参数 $m,k$ 执行 $m$ 次操作： 每次选出当前最大的 $k$ 个元素（值相同则下标小更大），把它们各 $-1$。

定义：

• $F_{m,k}(x)$：操作后数组非降序排序的第 $x$ 小值（第 $x$ 阶统计量）。
• $S_{m,k}(l,r)=\sum_{x=l}^r F_{m,k}(x)$。

要求：

1. 先输出 $F_{m_0,k_0}(1..n)$。
2. 处理 $q$ 个询问：
   • 单点修改 $a_p\leftarrow v$。
   • 查询 $F_{m,k}(x)$。
   • 查询 $S_{m,k}(l,r)$。

所有查询独立计算，不改变数组；修改永久生效。

---

二、核心观察（决定整个算法）

1. 操作等价描述

执行 $m$ 轮、每轮减 $k$ 个最大值，等价于：

对每个位置 $i$，设它被减了 $t_i$ 次，则

$$\sum_{i=1}^n t_i = m\cdot k$$

且满足单调性约束： 若 $a_i > a_j$ 或 $(a_i=a_j\land i<j)$，则 $t_i\ge t_j$。

2. 最终值形式

最终数组中元素 $i$ 的值为：

$$b_i = a_i - t_i$$

3. 关键转化：二分阈值

存在一个阈值 $V$，使得：

• 满足 $a_i - t_i \ge V$ 的元素数量 $\le k$；
• 满足 $a_i - t_i > V$ 的元素数量 $<k$。

我们可以二分答案 $V$，判断：

最多能执行多少次“减最大 $k$ 个”操作，使得所有 $b_i\ge V$。

这就是标程中 chk(t,m) 函数的本质。

---

三、核心函数：chk(t, m) 含义

定义：

$$\mathrm{chk}(V, m) = \sum_{a_i \ge V} \min(m,\ a_i - V) + \sum_{V-1 < a_i < V} (a_i - (V-1)) $$

直观意义：

把所有数“压到不低于 $V$”，至少需要减掉多少总量。

我们要二分最小的 $V$，满足

$$\mathrm{chk}(V, m) \le m\cdot k$$

这个 $V$ 就是最终数组的分界值，大部分数会落在 $V$ 或 $V-1$。

---

四、最终数组结构

二分得到分界值 $t$ 后，最终数组 $b_i$ 只有三类：

1. $b_i = t + m$：极大值，被减满 $m$ 次。
2. $b_i = t$：中间层，恰好减到阈值。
3. $b_i = t-1$：底层，减到阈值下一层。
4. 更小的数：原本就远小于阈值，不受影响。

标程中 mlen 就是恰好等于 $t$ 的元素个数。

---

五、求阶统计量与区间和

我们需要：

• 对最终 $b$ 数组排序；
• 求第 $x$ 小；
• 求区间 $[l,r]$ 的和。

1. 排序后取值分布

排序后数组从低到高：

• 一堆 $<t-1$ 的数；
• 一堆 $t-1$；
• 一堆 $t$；
• 一堆 $>t$ 的数。

2. 快速统计：树状数组 BIT

离散化所有 $a_i$ 与修改值，维护两颗 BIT：

• $\mathrm{cnt}$：统计值域上的元素个数；
• $\mathrm{val}$：统计值域上的元素和。

这样可以 $O(\log M)$ 完成：

• 个数前缀和 $\rightarrow$ 二分找第 $k$ 小；
• 和前缀和 $\rightarrow$ 区间和。

这就是标程 query_k 与 solve 的作用。

---

六、整体流程

步骤 1：离线离散化

把所有初始 $a_i$ 和所有修改操作的新值收集起来，离散化，压缩值域。

步骤 2：初始化 BIT

• $\mathrm{cnt.add(rk(a_i), 1)}$
• $\mathrm{val.add(rk(a_i), a_i)}$

步骤 3：处理初始输出 $F_{m_0,k_0}(1..n)$

对每个 $x\in[1,n]$：

• 二分阈值 $t$；
• 用 $\mathrm{solve}$ 计算排序后第 $x$ 小值；
• 输出。

步骤 4：处理询问

• 修改操作：在 BIT 中删去旧值，加入新值。
• 查询 1/3：调用 $\mathrm{work}(m,k,l,r)$，返回排序后 $[l,r]$ 的和。

---

七、关键函数公式化

1. 二分阈值

ll L = -INF, R = max_a;
while (L < R) {
    ll mid = (L + R) / 2;
    if (chk(mid, m) > m * k) L = mid + 1;
    else R = mid;
}

对应数学条件：

$$\mathrm{chk}(V, m) \le mk \quad\Rightarrow\quad \text{合法} $$

2. 统计第 k 小

ll qry(int l, int r, ll d)

表示：

值域 $[l,r]$ 中，取最大的 $d$ 个数的和。

利用 BIT 二分实现。

3. 总答案

$$S(l,r) = \mathrm{solve}(t,m,mlen, n-l+1) - \mathrm{solve}(t,m,mlen, n-r) $$

即排序后后缀和相减得到 $[l,r]$ 的和。

---

八、复杂度分析

• 离散化：$O((n+q)\log(n+q))$
• 单次询问 $\mathrm{work}$：
  • 二分 $V$：$O(\log A),\ A\le 2\cdot10^9$
  • 每次 $\mathrm{chk}$：$O(\log M)$
  • 统计 $\mathrm{solve}$：$O(\log M)$
• 总体：$$O((n+q)\log A \log M)$$ 可轻松通过 $n,q\le 2\cdot10^5$，时限 $4s$。