U570080 动态区间中位数查询与更新

给定一个初始长度为 $N$ 的整数数组 $A$，需要处理以下两种操作： 1. 更新操作 `U i x`：将下标为 $i$ 的元素 $A_i$ 更新为 $x$。 2. 查询操作 `Q l r`：查询区间 $[l, r]$ 的中位数。中位数定义为：将该区间内的所有数从小到大排序后，位于中间位置的数（如果区间内元素个数为偶数，则取中间两个数中较小的那个）。 请设计一个高效的数据结构，支持这两种操作。

- 第一行输入两个整数 $N$ 和 $M$，分别表示数组初始长度和操作次数。 - 第二行输入 $N$ 个整数，表示初始数组 $A$。 - 接下来 $M$ 行，每行一个操作，格式为 `U i x` 或 `Q l r`（下标从 $0$ 开始）。

- 对于每个查询操作，输出一行，表示查询结果。

#### 样例解释 - 初始数组为 $[1, 2, 3, 4, 5]$，第一次查询区间 $[0, 4]$ 的中位数，排序后为 $[1, 2, 3, 4, 5]$，中位数为 $3$。 - 将 $A_2$ 更新为 10 后，数组变为 $[1, 2, 10, 4, 5]$。 - 第二次查询区间 $[0, 4]$ 的中位数，排序后为 $[1, 2, 4, 5, 10]$，中位数为 $4$。 #### 数据范围 - $1 \leq N, M \leq 10^5$ - 数组元素和更新值均为整数，且在 $32$ 位整数范围内。 - $0 \leq i \leq N-1$, $0 \leq l \leq r \leq N-1$