← 返回题目列表

Codeforces · 1690/G

G. 数火车

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

铁轨上有$$$n$$$个独立车厢。车厢从左到右编号为 $$$1$$$ 到 $$$n$$$。车厢彼此不相连。车厢向左移动,因此编号为 $$$1$$$ 的车厢在所有车厢前面移动。

第$$$i$$$车厢有自己的发动机,可以将车厢加速到$$$a_i$$$公里/小时,但车厢不能比前面的车厢快。请参阅示例以获取解释。

所有车厢同时开始向左移动,它们自然形成火车。我们称火车为具有相同速度的连续移动的车厢。

例如,我们有 $$$n=5$$$ 车厢和数组 $$$a = [10, 13, 5, 2, 6]$$$。那么车厢的最终速度将是 $$$[10, 10, 5, 2, 2]$$$。分别将形成$$$3$$$的列车。

还有消息称某些引擎已损坏:

- 消息“k d”表示第 $$$k$$$ 个托架的速度已降低了 $$$d$$$(即,托架的最大速度 $$$a_k = a_k - d$$$ 发生了变化)。

消息按顺序到达,下一条消息的处理会考虑所有先前消息的更改。

在每条消息后确定形成的列车的数量。

输入

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

接下来是测试用例的描述。

每个测试用例的第一行是空的。

测试用例的第二行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n,m \le 10^5$$$) – 分别是车厢数量和减慢车厢速度的消息数量。

第三行包含$$$n$$$整数:$$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$)——数字$$$a_i$$$表示编号为$$$i$$$的车厢可以达到$$$a_i$$$公里/小时的速度。

接下来的 $$$m$$$ 行包含两个整数 $$$k_j$$$ 和 $$$d_j$$$ ($$$1 \le k_j \le n$$$, $$$0 \le d_j \le a_{k_j}$$$) - 这是编号为 $$$k_j$$$ 的车厢速度下降的消息$$$d_j$$$。换句话说,它的最大速度发生了变化$$$a_{k_j} = a_{k_j} - d_j$$$。请注意,任何时候每个托架的速度都是非负的。换句话说,$$$a_i \ge s_i$$$,其中$$$s_i$$$ - 是$$$d_j$$$ 的总和,使得$$$k_j=i$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。同样,保证所有测试用例的 $$$m$$$ 总和不超过 $$$10^5$$$。

输出

打印 $$$t$$$ 行。在每一行打印相应测试用例的答案。

对于每个测试用例,打印 $$$m$$$ 数字:每条消息后形成的列车数量。

示例

输入 #1

3
4 2
6 2 3 7
3 2
4 7
5 4
10 13 5 2 6
2 4
5 2
1 5
3 2
13 4
769 514 336 173 181 373 519 338 985 709 729 702 168
12 581
6 222
7 233
5 117

输出 #1

3 4 
4 4 2 3 
5 6 6 5

注意

对于第一个测试用例:

- 初始数组 $$$a = [6, 2, 3, 7]$$$。
- 在第一条消息之后,数组 $$$a = [6, 2, 1, 7]$$$。因此,车厢的速度为 $$$[6, 2, 1, 1]$$$,将形成火车的 $$$3$$$。
- 第二条消息之后,数组 $$$a = [6, 2, 1, 0]$$$。因此,车厢的速度为$$$[6,2,1,0]$$$,将形成火车的$$$4$$$。

对于第二个测试用例:

- 最初,数组 $$$a = [10, 13, 5, 2, 6]$$$。
- 在第一条消息之后,数组 $$$a = [10, 9, 5, 2, 6]$$$。因此,车厢的速度相等: $$$[10, 9, 5, 2, 2]$$$ 和 $$$4$$$ 的火车将形成。
- 第二条消息之后,数组 $$$a = [10, 9, 5, 2, 4]$$$。因此,车厢的速度为$$$[10,9,5,2,2]$$$,将形成火车的$$$4$$$。
- 第三条消息之后,数组 $$$a = [5, 9, 5, 2, 4]$$$。因此,车厢的速度为 $$$[5, 5, 5, 2, 2]$$$,将形成火车 $$$2$$$。
- 在第四条消息之后,数组 $$$a = [5, 9, 3, 2, 4]$$$。因此,车厢的速度为 $$$[5, 5, 3, 2, 2]$$$,将形成火车 $$$3$$$。