阶统计量（Order Statistics）

题目翻译（规范中文 + 公式格式）

问题描述

给定一个由整数组成的数组 $a_1,a_2,\dots,a_n$，以及整数 $k$ 和 $m$。对数组执行 $m$ 次如下操作：

1. 选出数组中最大的 $k$ 个元素的下标 $i_1,i_2,\dots,i_k$。若两个元素值相等，下标更小的元素视为更大。
2. 将 $a_{i_1},a_{i_2},\dots,a_{i_k}$ 各自减 $1$。

定义：

• 对于 $x \in [1,n]$，$F_{m,k}(x)$ 表示对原数组执行 $m$ 次参数为 $k$ 的操作后，数组的第 $x$ 阶统计量。
• 数组的第 $x$ 阶统计量：将数组非降序排序后，位于位置 $x$ 上的元素。
• 对于 $1 \le l \le r \le n$，$S_{m,k}(l,r)$ 表示 $F_{m,k}(x)$ 在 $x \in [l,r]$ 上的和。 形式化定义：$$S_{m,k}(l,r) = \sum_{x=l}^{r} F_{m,k}(x)$$

给定初始参数 $m_0, k_0$，你需要：

1. 计算并输出 $F_{m_0,k_0}(x) \ (x=1..n)$。
2. 处理 $q$ 个询问，询问共三种类型：
   • 类型 1：查询 $F_{m_j,k_j}(x_j)$ 的值。
   • 类型 2：将数组中 $a_{p_j}$ 的值修改为 $v_j$（修改永久生效）。
   • 类型 3：查询 $S_{m_j,k_j}(l_j,r_j)$ 的值。

重要规则：

• 所有 $F$ 和 $S$ 的计算相互独立，不会改变原数组。
• 类型 2 的修改永久生效，会影响后续所有询问。

---

输入格式

第一行包含四个整数 $n, m_0, k_0, q$ $(1 \le n \le 2 \times 10^5,\ 0 \le m_0 \le 10^9,\ 1 \le k_0 \le n,\ 0 \le q \le 2 \times 10^5)$ 分别表示：数组长度、初始操作次数、初始每次减 $1$ 的元素个数、询问次数。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$ $(-10^9 \le a_i \le 10^9)$ 表示初始数组。

接下来 $q$ 行，每行描述一个询问，首个数字为询问类型 $t_j$：

1. 若 $t_j=1$，后续跟着三个整数 $m_j,k_j,x_j$ $(0 \le m_j \le 10^9,\ 1 \le k_j,x_j \le n)$
2. 若 $t_j=2$，后续跟着两个整数 $p_j,v_j$ $(1 \le p_j \le n,\ -10^9 \le v_j \le 10^9)$
3. 若 $t_j=3$，后续跟着四个整数 $m_j,k_j,l_j,r_j$ $(0 \le m_j \le 10^9,\ 1 \le k_j,l_j,r_j \le n,\ l_j \le r_j)$

---

输出格式

第一行输出 $n$ 个整数，表示 $F_{m_0,k_0}(1), F_{m_0,k_0}(2), \dots, F_{m_0,k_0}(n)$。

对于每个询问：

• 类型 1：单独一行输出 $F_{m_j,k_j}(x_j)$。
• 类型 3：单独一行输出 $S_{m_j,k_j}(l_j,r_j)$。

---

样例输入输出

标准输入

8 3 2 16
3 1 2 -1 0 2 -1 4
3 3 2 2 6
1 3 2 4
3 4 5 3 5
1 4 5 6
2 5 -1
2 6 3
1 3 2 1
1 3 2 3
1 3 2 4
1 3 2 8
1 0 5 6
2 1 5
3 1 3 7 8
3 2 3 5 8
3 3 3 4 7
3 4 3 4 7

标准输出

-1 -1 0 1 1 1 1 2
2
1
-4
-1
-1
-1
-1
1
2
3
7
8
4
2

---

样例解释

$n=8,\ m_0=3,\ k_0=2$，初始数组：$[3,1,2,-1,0,2,-1,4]$ 执行 $3$ 次操作（每次选最大的 $2$ 个元素减 $1$）：

1. 最大元素：位置 $1,8$ → 数组变为 $[2,1,2,-1,0,2,-1,3]$
2. 最大元素：位置 $1,8$ → 数组变为 $[1,1,2,-1,0,2,-1,2]$
3. 最大元素：位置 $3,6$ → 数组变为 $[1,1,1,-1,0,1,-1,2]$

将最终数组排序得：$[-1,-1,0,1,1,1,1,2]$ 因此 $F_{3,2}(x)$ 就是排序后的数组，与输出第一行一致。

---

数据范围与评分

• 数组长度、询问数：$n,q \le 2 \times 10^5$
• 操作次数：$m \le 10^9$
• 元素值域：$a_i \in [-10^9,10^9]$
• 时间限制：$4$ 秒
• 空间限制：$1024$ MB