← 返回题目列表

Codeforces · 2029/G

G. 平衡问题

中文机器翻译题面 查看原题

有一个数组 $$$a$$$ 由 $$$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 给了你一个整数 $$$V$$$,你需要解决每个 $$$1\le v\le V$$$ 的问题。

输入

每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1\let 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$$$ 行,第 $$$i$$$ 行包含字符 $$$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$$$ 个整数,第 $$$i$$$ 个整数表示当 $$$v=i$$$ 时 Kevin 执行一些新操作后的最大可能的美感。

示例

输入 #1

5
3 3 2
1 2 4
L 3
R 3
L 1
3 3 2
5 1 4
L 3
R 3
L 1
5 4 5
1 1 1 1 1
L 3
R 2
L 5
L 4
10 12 9
10 9 8 7 6 5 4 3 2 1
L 2
L 4
R 4
R 4
L 6
R 8
L 3
L 2
R 1
R 10
L 8
L 1
1 1 4
1000000000
L 1

输出 #1

2 6
1 9
0 1 3 5 5
0 0 0 6 25 32 35 44 51
1000000000 1000000000 1000000000 1000000000

注意

在第一个测试用例中,数组 $$$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$$$ 来说,最好不执行任何新操作。