[AdditionalFile5360.zip](file://AdditionalFile5360.zip?type=additional_file)

#5360. 「OOI 2025 Day 2」顺序统计量

标签: 传统 | 时间限制: 4000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2025 Day2 T4 「Порядковая статистика / Order Statistics」。

给定一个包含 $n$ 个整数的数组 $a_1, a_2, \ldots, a_n$，以及整数 $k$ 和 $m$。对该数组执行 $m$ 次以下操作：

• 选择 $i_1, i_2, \ldots, i_k$，即数组 $a$ 中 $k$ 个最大元素的编号。如果两个元素相等，则编号较小的元素视为较大。
• 将 $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ 各减去 $1$。

对于 $x$ 从 $1$ 到 $n$，定义 $F_{m,k}(x)$ 为从数组 $a$ 经过 $m$ 次参数为 $k$ 的操作后得到的数组的第 $x$ 个顺序统计量。对于 $x$ 从 $1$ 到 $n$，数组 $a_1, a_2, \ldots, a_n$ 的第 $x$ 个顺序统计量是指将数组按非递减顺序排序后位于第 $x$ 位的元素。

对于所有满足 $1 \leq l \leq r \leq n$ 的 $l$ 和 $r$，定义 $S_{m,k}(l,r)$ 为 $F_{m,k}(x)$ 从 $x = l$ 到 $x = r$ 的总和，即：

$$S_{m,k}(l,r) = \sum_{x=l}^{r} F_{m,k}(x)$$

给定整数 $m_0$ 和 $k_0$。你需要计算对于所有 $x$ 从 $1$ 到 $n$ 的 $F_{m_0,k_0}(x)$ 值。

之后，你需要处理 $q$ 个查询。第 $j$ $(1 \leq j \leq 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$ 的计算都是独立的，不改变数组。所有第二类查询对数组的修改将保留到后续查询中。

输入格式

第一行包含四个整数 $n, m_0, k_0, q$ $(1 \leq n \leq 200000, 0 \leq m_0 \leq 10^{9}, 1 \leq k_0 \leq n, 0 \leq q \leq 200000)$，分别表示数组 $a$ 的长度、操作次数、每次操作减少的最大元素个数和查询数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(-10^{9} \leq a_i \leq 10^{9}, 1 \leq i \leq n)$，表示数组 $a$ 的元素。

接下来的 $q$ 行描述查询。第 $j$ 行开头是一个整数 $t_j$ $(1 \leq t_j \leq 3)$，表示第 $j$ 个查询的类型。

• 如果 $t_j=1$，则接下来有三个整数 $m_j, k_j, x_j$ $(0 \leq m_j \leq 10^{9}, 1 \leq k_j, x_j \leq n)$，表示第一类查询的参数。
• 如果 $t_j=2$，则接下来有两个整数 $p_j$ 和 $v_j$ $(1 \leq p_j \leq n, -10^{9} \leq v_j \leq 10^{9})$，表示第二类查询的参数。
• 如果 $t_j=3$，则接下来有四个整数 $m_j, k_j, l_j, r_j$ $(0 \leq m_j \leq 10^{9}, 1 \leq k_j, l_j, r_j \leq n, l_j \leq 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$ 个查询的回答。

样例

输入

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
2
3
7
8
4
2

在样例中，$n=8$，$m_0=3$，$k_0=2$，$q=16$。初始数组 $a$ 为 $[3, 1, 2, -1, 0, 2, -1, 4]$。我们来看看数组在执行 $m_0$ 次参数为 $k_0$ 的操作后的变化：

1. 数组为 $[3,1,2,-1,0,2,-1,4]$。两个最大元素位于编号 $1$ 和 $8$。将它们减去 $1$ 后，数组变为 $[2,1,2,-1,0,2,-1,3]$。
2. 数组为 $[2,1,2,-1,0,2,-1,3]$。两个最大元素位于编号 $1$ 和 $8$。将它们减去 $1$ 后，数组变为 $[1,1,2,-1,0,2,-1,2]$。
3. 数组为 $[1,1,2,-1,0,2,-1,2]$。两个最大元素位于编号 $3$ 和 $6$。将它们减去 $1$ 后，数组变为 $[1,1,1,-1,0,1,-1,2]$。

因此，经过 $3$ 次参数为 $2$ 的操作后，数组 $a$ 变为 $[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$ 个查询：

1. 第一个查询类型为 $t_1=3$，参数为 $m_1=3$，$k_1=2$，$l_1=2$，$r_1=6$，要求计算 $S_{3,2}(2,6)$。我们已经计算了 $F_{3,2}(x)$ 对于 $x$ 从 $1$ 到 $8$ 的值，因此查询答案为：

$$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$$

2. 第二个查询类型为 $t_2=1$，参数为 $m_2=3$，$k_2=2$，$x_2=4$，要求计算 $F_{3,2}(4)$。我们已经计算过，其值为 $1$。
3. 第三个查询类型为 $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$ 的操作后，得到的数组的第 $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$$

4. 第四个查询类型为 $t_4=1$，参数为 $m_4=4$，$k_4=5$，$x_4=6$。经过四次参数为 $5$ 的操作并排序后，数组为 $[-2,-2,-2,-1,-1,-1,-1,0]$，因此第六个顺序统计量为 $-1$。
5. 第五个查询类型为 $t_5=2$，参数为 $p_5=5$ 和 $v_5=-1$。它将 $a_5$ 的值修改为 $-1$，之后数组 $a$ 变为 $[3,1,2,-1,-1,2,-1,4]$。
6. 第六个查询类型为 $t_6=2$，参数为 $p_6=6$ 和 $v_6=3$。它将 $a_6$ 的值修改为 $3$，之后数组 $a$ 变为 $[3,1,2,-1,-1,3,-1,4]$。
7. 第七个查询要求计算 $F_{3,2}(1)$ 的值。在第七个查询时，数组 $a$ 为 $[3,1,2,-1,-1,3,-1,4]$。经过 $3$ 次参数为 $2$ 的操作后，数组变为 $[1,1,1,-1,-1,2,-1,2]$。第一个顺序统计量为 $-1$。
8. 第八、九、十个查询要求计算 $F_{3,2}(3)$、$F_{3,2}(4)$ 和 $F_{3,2}(8)$ 的值，即数组 $[1,1,1,-1,-1,2,-1,2]$ 的第三、第四和第八个顺序统计量，分别为 $-1$、$1$ 和 $2$。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。

子任务	分值	附加限制	子任务依赖	备注
$1$	$4$	$n \leq 1000$，$m \leq 1000$		$q=0$
$2$	$5$	$k=1$
$3$	$6$		$2$	$q \leq 100000$，所有查询类型为 $t_j=1$
$4$	$7$		$2, 3$	$q \leq 100000$，所有查询类型不为 $t_j=3$
$5$	$11$	$k=2$		$q=0$
$6$	$9$	$m \leq 10^{6}$	$1$
$7$	$10$	$n \leq 1000$	$1$
$8$	$7$		$1, 2, 5 \sim 7$
$9$	$11$		$1 \sim 3, 5 \sim 8$	$q \leq 100000$，所有查询类型为 $t_j=1$
$10$	$13$		$1 \sim 3, 5 \sim 9$	$q \leq 100000$，所有查询类型不为 $t_j=2$
$11$	$9$		$0 \sim 10$	$q \leq 100000$
$12$	$8$		$0 \sim 11$