Even-Odd Increments Ⅱ

时间限制：1000ms

空间限制：256MB

题目描述

给定包含 $n$ 个整数的有序数组 $\{a_0, a_1, \cdots, a_{n-1}\}$，处理 $q$ 个包含两种类型 ( $type$ ) 的询问：

类型为 “$0\, x$” 的询问：将值 $x$ 加到数组 $a$ 的所有偶数下标的元素上；

类型为 “$1\,x$” 的询问：将值 $x$ 加到数组 $a$ 的所有奇数下标的元素上；

处理每个询问后，给数组 $a$ 重新排序，之后输出数组 $a$ 中奇数下标的元素之和。

输入格式

第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 1e4$），表示数组 $a$ 的长度和询问的数量；

第二行包含 $n$ 个整数，为有序数组 $a$ 的元素（$1 \leq a \leq 1e9$）。

接下来的 $q$ 行为询问，由两个整数 $type$（ $0$ 或 $1$ ） 和 $x$ 组成（$1 \leq x \leq 1e4$）。

输出格式

输出 $q$ 行整数，代表处理完一个询问以及排序后，数组 $a$ 中奇数下标的元素之和。

样例输入1

3 3
1 2 4
0 2
1 3 
0 5

样例输出1

3
6
7

样例1解释

第1次询问+排序：3 2 6 $\to$ 2 3 6,奇数下标元素和：3

第2次询问+排序：2 6 6 $\to$ 2 6 6,奇数下标元素和：6

第3次询问+排序：7 6 11 $\to$ 6 7 11,奇数下标元素和：7

样例输入2

6 5
1 3 3 4 10 48
1 6
0 5
0 4
0 5
1 3

样例输出2

67
74
75
84
93 

样例2解释

第1次询问+排序：1 9 3 10 10 54 $\to$ 1 3 9 10 10 54,奇数下标元素和：$3+10+54=67$

第2次询问+排序：6 3 14 10 15 54 $\to$ 3 6 10 14 15 54,奇数下标元素和：$6+14+54=74$

第3次询问+排序：7 6 14 14 19 54 $\to$ 6 7 14 14 19 54,奇数下标元素和：$7+14+54=75$

第4次询问+排序：11 7 19 14 24 54 $\to$ 7 11 14 19 24 54,奇数下标元素和：$11+19+54=84$

第5次询问+排序：7 14 14 22 24 57 $\to$ 7 14 14 22 24 57,奇数下标元素和：$14+22+57=93$

数据范围及约定

对于 $60\%$ 的数据，$n \leq 100, q \leq 100$

对于 $100\%$ 的数据，$n \leq 1e4, q \leq 1e4$