P12080 [OOI 2025] Order Statistics

[试题来源](https://inf-open.ru/2024-25/final-materials/)。

给定一个由整数组成的数组 $a_1, a_2, \ldots, a_n$，以及整数 $k$ 和 $m$。 对该数组执行以下操作 $m$ 次： - 选出数组 $a$ 中 $k$ 个最大元素的位置 $i_1, i_2, \ldots, i_k$。如果两个元素相等，则认为数组中较早出现的元素更大。 - 将 $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ 的值各减 $1$。 对于从 $1$ 到 $n$ 的 $x$，令 $F_{m,k}(x)$ 表示对数组 $a$ 应用 $m$ 次参数为 $k$ 的操作后得到的数组中第 $x$ 个顺序统计量的值。对于从 $1$ 到 $n$ 的 $x$，数组 $a_1, a_2, \ldots, a_n$ 的第 $x$ 个顺序统计量是指如果将数组 $a$ 按非递减顺序排序后，位于位置 $x$ 的元素。 对于所有满足 $1 \le l \le r \le n$ 的 $l, r$，令 $S_{m,k}(l,r)$ 表示所有从 $l$ 到 $r$ 的整数 $x$ 的 $F_{m,k}(x)$ 之和。 更正式地： $$ S_{m,k}(l,r)=\sum_{x=l}^r F_{m,k}(x) $$ 给定整数 $m_0$ 和 $k_0$。 你必须计算所有从 $1$ 到 $n$ 的 $x$ 的 $F_{m_0,k_0}(x)$ 的值。 之后，你必须处理 $q$ 个查询。第 $j$ 个查询（$1 \le j \le q$）可以是以下三种类型之一： - 计算 $F_{m_j,k_j}(x_j)$ 的值。 - 将 $a_{p_j}$ 的值修改为 $v_j$。 - 计算 $S_{m_j,k_j}(l_j,r_j)$ 的值。 所有函数 $F$ 和 $S$ 的计算每次都是独立进行的，并且不会改变数组。第二种类型查询对数组的所有修改都会保留到后续查询中。

第一行包含四个整数 $n$、$m_0$、$k_0$ 和 $q$（$1 \le n \le 200\,000$，$0 \le m_0 \le 10^9$，$1 \le k_0 \le n$，$0 \le q \le 200\,000$）—— 分别表示数组 $a$ 的长度、操作次数、每次操作中减少的最大的元素数量以及查询的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \le a_i \le 10^9$，$1 \le i \le n$）—— 数组 $a$ 的元素。 接下来的 $q$ 行包含查询。在第 $j$ 个查询中，第一个数字是 $t_j$（$1 \le t_j \le 3$）—— 第 $j$ 个查询的类型。 - 如果 $t_j=1$，则下一行包含三个整数 $m_j$、$k_j$ 和 $x_j$（$0 \le m_j \le 10^9$，$1 \le k_j, x_j \le n$）—— 第一类查询的参数。 - 如果 $t_j=2$，则下一行包含两个整数 $p_j$ 和 $v_j$（$1 \le p_j \le n$，$-10^9 \le v_j \le 10^9$）—— 第二类查询的参数。 - 如果 $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), \ldots, F_{m_0,k_0}(n)$。 然后，对于每个第一类查询，单独一行输出值 $F_{m_j, k_j}(x_j)$；对于每个第三类查询，单独一行输出值 $S_{m_j, k_j}(l_j, r_j)$ —— 即第 $j$ 个查询的答案。

**样例解释** 在样例中，$n=8$，$m_0=3$，$k_0=2$，$q=16$。初始时，数组 $a$ 为 $[3, 1, 2, -1, 0, 2, -1, 4]$。 让我们看看如果用参数 $k_0$ 对数组应用 $m_0$ 次操作，数组会如何变化： - 数组为 $[3,1,2,-1,0,2,-1,4]$。两个最大的元素位于位置 $1$ 和 $8$。将它们减 $1$ 后，数组变为 $[2,1,2,-1,0,2,-1,3]$。 - 数组为 $[2,1,2,-1,0,2,-1,3]$。两个最大的元素位于位置 $1$ 和 $8$。将它们减 $1$ 后，数组变为 $[1,1,2,-1,0,2,-1,2]$。 - 数组为 $[1,1,2,-1,0,2,-1,2]$。两个最大的元素位于位置 $3$ 和 $6$。将它们减 $1$ 后，数组变为 $[1,1,1,-1,0,1,-1,2]$。 我们发现，对数组 $a$ 应用 $3$ 次参数为 $2$ 的操作后，它变成了 $[1,1,1,-1,0,1,-1,2]$。如果对这个数组排序，会得到数组 $[-1,-1,0,1,1,1,1,2]$。因此，顺序统计量为 $F_{3,2}(1)=-1$，$F_{3,2}(2)=-1$，$F_{3,2}(3)=0$，$F_{3,2}(4)=1$，$F_{3,2}(5)=1$，$F_{3,2}(6)=1$，$F_{3,2}(7)=1$，$F_{3,2}(8)=2$。 在样例中，我们需要处理 $16$ 个查询；让我们详细分析前 $10$ 个查询： - 第一个查询类型为 $t_1=3$，参数为 $m_1=3$，$k_1=2$，$l_1=2$，$r_1=6$，需要计算 $S_{3,2}(2,6)$ 的值。我们已经计算了从 $1$ 到 $8$ 的 $x$ 的 $F_{3,2}(x)$ 值，由此可以找到查询的答案：$$S_{3,2}(2,6)=F_{3,2}(2)+F_{3,2}(3)+F_{3,2}(4)+F_{3,2}(5)+F_{3,2}(6)=(-1)+0+1+1+1=2$$ - 第二个查询类型为 $t_2=1$，参数为 $m_2=3$，$k_2=2$，$x_2=4$，需要计算 $F_{3,2}(4)$ 的值。我们已经计算过，它等于 $1$。 - 第三个查询类型为 $t_3=3$，参数为 $m_3=4$，$k_3=5$，$l_3=3$，$r_3=5$，需要计算 $S_{4,5}(3,5)$ 的值，即计算对数组 $a$ 应用 $m_3=4$ 次参数为 $k_3=5$ 的操作后得到的数组中，从第三个到第五个顺序统计量的和。在第三个查询时，数组 $a$ 为 $[3, 1, 2, -1, 0, 2, -1, 4]$。五个最大的元素位于位置 $1,2,3,6,8$。将它们减 $1$，得到数组 $[2,0,1,-1,0,1,-1,3]$。再应用三次操作，得到数组 $[-1,-2,-2,-2,-1,-1,-1,0]$。排序后变为 $[-2,-2,-2,-1,-1,-1,-1,0]$。因此，查询的答案是 $$S_{4,5}(3,5)=F_{4,5}(3)+F_{4,5}(4)+F_{4,5}(5)=(-2)+(-1)+(-1)=-4$$ - 第四个查询类型为 $t_4=1$，参数为 $m_4=4$，$k_4=5$，$x_4=6$。在应用 $4$ 次参数为 $5$ 的操作并对数组 $a$ 排序后，数组将变为 $[-2,-2,-2,-1,-1,-1,-1,0]$，所以第六个顺序统计量是 $-1$。 - 第五个查询类型为 $t_5=2$，参数为 $p_5=5$ 和 $v_5=-1$。它将 $a_5$ 的值修改为 $-1$，之后数组 $a$ 变为 $[3,1,2,-1,-1,2,-1,4]$。 - 第六个查询类型为 $t_6=2$，参数为 $p_6=6$ 和 $v_6=3$。它将 $a_6$ 的值修改为 $3$，之后数组 $a$ 变为 $[3,1,2,-1,-1,3,-1,4]$。 - 第七个查询需要找到 $F_{3,2}(1)$ 的值。在第七个查询时，数组 $a$ 为 $[3,1,2,-1,-1,3,-1,4]$。应用 $3$ 次参数为 $2$ 的操作后，它将变为 $[1, 1, 1, -1, -1, 2, -1, 2]$。这个数组的第一个顺序统计量是 $-1$。 - 第八、第九和第十个查询需要找到 $F_{3,2}(3)$、$F_{3,2}(4)$ 和 $F_{3,2}(8)$ 的值，即数组 $[1, 1, 1, -1, -1, 2, -1, 2]$ 中的第三、第四和第八个顺序统计量。它们分别等于 $-1$、$1$ 和 $2$。 **说明提示** 本题的测试点包含十二个分组。每个分组的分数只有在该分组的所有测试点以及所有依赖分组的测试点都通过时才能获得。请注意，通过样例测试点对于某些分组不是必需的。**Offline-evaluation** 表示该分组的测试结果将在比赛结束后才可查看。 如果某个子任务对 $m$ 或 $k$ 有限制，那么这些限制同时适用于 $m_0$ 和 $k_0$，以及所有第一类和第三类查询的参数。 | Subtask | 分数 | 限制条件：$n$ | $m$ | $k$ | $q$ | 依赖组别 | 说明 | | :--- | :--- | :------------- | :-- | :-- | :-- | :-------- | :---- | | 0 | 0 | -- | -- | -- | -- | -- | 样例测试点。 | | 1 | 4 | $n \le 1000$ | $m \le 1000$ | -- | $q=0$ | -- | -- | | 2 | 5 | -- | -- | $k=1$ | $q=0$ | -- | -- | | 3 | 6 | -- | -- | $k=1$ | $q \le 100\,000$ | 2 | 所有查询中 $t_j=1$。 | | 4 | 7 | -- | -- | $k=1$ | $q \le 100\,000$ | 2, 3 | 所有查询中 $t_j \ne 3$。 | | 5 | 11 | -- | -- | $k=2$ | $q=0$ | -- | -- | | 6 | 9 | -- | $m \le 10^6$ | -- | $q=0$ | 1 | -- | | 7 | 10 | $n \le 1000$ | -- | -- | $q=0$ | 1 | -- | | 8 | 7 | -- | -- | -- | $q=0$ | 1, 2, 5 -- 7 | -- | | 9 | 11 | -- | -- | -- | $q \le 100\,000$ | 1 -- 3, 5 -- 8 | 所有查询中 $t_j=1$。 | | 10 | 13 | -- | -- | -- | $q \le 100\,000$ | 1 -- 3, 5 -- 9 | 所有查询中 $t_j\ne 2$。 | | 11 | 9 | -- | -- | -- | $q \le 100\,000$ | 0 -- 10 | -- | | 12 | 8 | -- | -- | -- | -- | 0 -- 11 | **Offline-evaluation.** |