← 返回题目列表

Codeforces · 1744/B

B. 偶数-奇数增量

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

给你 $$$n$$$ 个整数 $$$a_1, a_2, \ldots, a_n$$$。处理两种类型的 $$$q$$$ 查询:

- 形式为“0 $$$x_j$$$”的查询:将值 $$$x_j$$$ 添加到数组 $$$a$$$ 的所有偶数元素,
- “1 $$$x_j$$$”形式的查询:将值 $$$x_j$$$ 添加到数组 $$$a$$$ 的所有奇数元素中。

请注意,在处理查询时,我们专门查看 $$$a_i$$$ 的奇/偶值,而不是其索引。

处理每个查询后,打印数组 $$$a$$$ 的元素之和。

请注意,某些测试用例的答案不适合 32 位整数类型,因此您应该在编程语言中至少使用 64 位整数类型(例如 C++ 的 long long)。

输入

输入的第一行包含一个整数 $$$t$$$ $$$(1 \leq t \leq 10^4$$$) — 测试用例的数量。

测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \leq n$$$, $$$q \leq 10^5$$$) — 数组 $$$a$$$ 的长度和查询的数量。

每个测试用例的第二行恰好包含 $$$n$$$ 整数: $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 数组 $$$a$$$ 的元素。

以下 $$$q$$$ 行包含作为两个整数 $$$type_j$$$ 和 $$$x_j$$$ $$$(0 \leq type_j \leq 1$$$, $$$1 \leq x_j \leq 10^4$$$) 的查询。

保证测试中所有测试用例的值 $$$n$$$ 之和不超过 $$$10^5$$$。同样,所有测试用例的值 $$$q$$$ 之和不超过 $$$10^5$$$。

输出

对于每个测试用例,打印 $$$q$$$ 数字:处理查询后数组 $$$a$$$ 的元素之和。

示例

输入 #1

4
1 1
1
1 1
3 3
1 2 4
0 2
1 3
0 5
6 7
1 3 2 4 10 48
1 6
0 5
0 4
0 5
1 3
0 12
0 1
6 7
1000000000 1000000000 1000000000 11 15 17
0 17
1 10000
1 51
0 92
0 53
1 16
0 1

输出 #1

2
11
14
29
80
100
100
100
118
190
196
3000000094
3000060094
3000060400
3000060952
3000061270
3000061366
3000061366

注意

在第一个测试用例中,第一个查询之后的数组 $$$a = [2]$$$。

在第三个测试用例中,数组 $$$a$$$ 修改如下: $$$[1, 3, 2, 4, 10, 48]$$$ $$$\rightarrow$$$ $$$[7, 9, 2, 4, 10, 48]$$$ $$$\rightarrow$$$ $$$[7, 9, 7, 9, 15, 53]$$$ $$$\rightarrow$$$ $$$[7, 9, 7, 9, 15, 53]$$$ $$$\rightarrow$$$ $$$[10, 12, 10, 12, 18, 56]$$$ $$$\rightarrow$$$ $$$[22, 24, 22, 24, 30, 68]$$$$$$\rightarrow$$$$$$[23,25,23,25,31,69]$$$。