CF2029G.Balanced Problem

有一个长度为 $n$ 的整数数组 $a$，初始时所有元素均为 $0$。

Kevin 可以对数组进行若干次操作。每次操作有以下两种类型之一：

• 前缀加法 —— Kevin 选择一个下标 $x$（$1\le x\le n$），然后对每个 $1\le j\le x$，将 $a_j$ 增加 $1$；
• 后缀加法 —— Kevin 选择一个下标 $x$（$1\le x\le n$），然后对每个 $x\le j\le n$，将 $a_j$ 增加 $1$。

在 KDOI 国，人们认为整数 $v$ 是“平衡”的。因此，Iris 给了 Kevin 一个长度为 $n$ 的数组 $c$，并定义数组 $a$ 的美丽值如下：

• 初始时，令 $b=0$；
• 对于每个 $1\le i\le n$，如果 $a_i=v$，则将 $c_i$ 加到 $b$ 上；
• $a$ 的美丽值即为最终的 $b$。

Kevin 想要在所有操作完成后，使 $a$ 的美丽值最大。然而，他在犯困时已经进行了 $m$ 次操作。现在，他可以再进行任意次数（可能为零）的新操作。

你需要帮助 Kevin，若他最优地进行新操作，求出最大可能的美丽值。

不过，为了防止你只是“碰运气”，Kevin 给了你一个整数 $V$，你需要对于每个 $1\le v\le V$ 都解决这个问题。

每组测试数据包含多个测试用例。输入的第一行包含一个整数 $t$（$1\le t\le 1000$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$m$ 和 $V$（$1\le n, m\le 2\cdot 10^5$，$1\le V\le 2000$），分别表示数组 $a$ 的长度、初始操作次数和 Kevin 给你的整数。

第二行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$（$1\le c_i\le 10^9$），表示数组 $c$ 的元素。

接下来 $m$ 行，每行包含一个字符 $op$ 和一个整数 $x$（$op=\mathtt{L}$ 或 $\mathtt{R}$，$1\le x\le n$），表示第 $i$ 次操作的类型和选择的下标。

• 如果 $op=\mathtt{L}$，则该操作为对下标 $x$ 的前缀加法；
• 如果 $op=\mathtt{R}$，则该操作为对下标 $x$ 的后缀加法。

保证：

• 所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$；
• 所有测试用例中 $m$ 的总和不超过 $2\cdot 10^5$；
• 所有测试用例中 $V^2$ 的总和不超过 $4\cdot 10^6$。

对于每个测试用例，输出 $V$ 个整数，表示当 $v=1,2,\ldots,V$ 时，Kevin 最优操作后能获得的最大美丽值。每组输出占一行。

在第一个测试用例中，数组 $a$ 在初始操作后变化如下：$[0, 0, 0] \xrightarrow{\mathtt{L}\ 3} [1, 1, 1] \xrightarrow{\mathtt{R}\ 3} [1, 1, 2] \xrightarrow{\mathtt{L}\ 1} [2, 1, 2]$。

• 对于 $v=1$，最优策略是不进行任何新操作，美丽值为 $b=c_2=2$；
• 对于 $v=2$，最优策略是在下标 $2$ 进行一次前缀加法，之后 $a$ 变为 $[3,2,2]$，美丽值为 $b=c_2+c_3=6$。

在第二个测试用例中，对于 $v=1$ 和 $v=2$，最优策略都是不进行任何新操作。

由 ChatGPT 4.1 翻译