Count the Trains

题意翻译

**【题目大意】** 铁轨上有 $n$ 节车厢，每节车厢在各自的引擎驱动下可以达到一个最高速度，记录在一个序列 $\{a_i\}$ 里. 车厢从左到右的编号依次为 $1$ 到 $n$. 现在让这些车厢向左尽可能快地开动，要求靠右的车厢实际速度不能超过靠左的车厢. 这样便会形成若干段速度一致的连续数节车厢，称这样的一段为**一节火车**. 例如序列 $a=[10,13,5,2,6]$ 对应的车厢的实际运行速度为 $[10,10,5,2,2]$，形成了 $3$ 节火车. 在车厢行驶时，依次收到了 $m$ 条形如 $k\ d$ 的信息，表示第 $k$ 节车厢的最高速度因引擎老化而下降了 $d$. 请维护这个过程中火车的总节数，每次收到信息后输出. **【输入格式】** 输入的第一行为测试用例数 $t$. 每个测试用例的第 $1$ 行为空，第 $2$ 行为 $n$ 和 $m$，第 $3$ 行为序列 $\{a_i\}_{i=1}^n$，接下来 $m$ 行每行给出一条信息 $k_i\ d_i$. **【输出格式】** 输出 $t$ 行对应 $t$ 个测试用例，每行用空格分隔 $m$ 个整数，表示收到每条信息后的火车节数. **【数据范围】** 所有数值均为整数. $t∈[1,10^4];$ $n,m∈[1,10^5];$ $a_i∈[0,10^9](\forall i∈[1,n]);$ $k_j∈[1,n],\ d_j∈[0,a_{k_j}](\forall j∈[1,m])$. 所有测试用例的 $n$ 的总和及 $m$ 的总和均不超过 $10^5$.

题目描述

There are $ n $ of independent carriages on the rails. The carriages are numbered from left to right from $ 1 $ to $ n $ . The carriages are not connected to each other. The carriages move to the left, so that the carriage with number $ 1 $ moves ahead of all of them. The $ i $ -th carriage has its own engine, which can accelerate the carriage to $ a_i $ km/h, but the carriage cannot go faster than the carriage in front of it. See example for explanation. All carriages start moving to the left at the same time, and they naturally form trains. We will call trains — consecutive moving carriages having the same speed. For example, we have $ n=5 $ carriages and array $ a = [10, 13, 5, 2, 6] $ . Then the final speeds of the carriages will be $ [10, 10, 5, 2, 2] $ . Respectively, $ 3 $ of the train will be formed. There are also messages saying that some engine has been corrupted: - message "k d" means that the speed of the $ k $ -th carriage has decreased by $ d $ (that is, there has been a change in the maximum speed of the carriage $ a_k = a_k - d $ ). Messages arrive sequentially, the processing of the next message takes into account the changes from all previous messages. After each message determine the number of formed trains.

输入输出格式

输入格式

The first line of input data contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) —the number of input test cases. This is followed by descriptions of the test cases. The first line of each test case is empty. The second line of the test case contains two integers $ n $ and $ m $ ( $ 1 \le n,m \le 10^5 $ ) —the number of carriages and the number of messages to slow down the carriage, respectively. The third line contains $ n $ integers: $ a_1, a_2, \dots, a_n $ ( $ 0 \le a_i \le 10^9 $ ) — the number $ a_i $ means that the carriage with number $ i $ can reach a speed of $ a_i $ km/h. The next $ m $ lines contain two integers $ k_j $ and $ d_j $ ( $ 1 \le k_j \le n $ , $ 0 \le d_j \le a_{k_j} $ ) —this is the message that the speed of the carriage with number $ k_j $ has decreased by $ d_j $ . In other words, there has been a change in its maximum speed $ a_{k_j} = a_{k_j} - d_j $ . Note that at any time the speed of each carriage is non-negative. In other words, $ a_i \ge s_i $ , where $ s_i $ —is the sum of such $ d_j $ that $ k_j=i $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ . Similarly, it is guaranteed that the sum of $ m $ over all test cases does not exceed $ 10^5 $ .

输出格式

Print $ t $ lines. On each line print the answer for the corresponding test case. For each test case print $ m $ numbers: the number of trains formed after each message.

输入输出样例

输入样例 #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

说明

For the first test case: - Initially array $ a = [6, 2, 3, 7] $ . - After the first message, the array $ a = [6, 2, 1, 7] $ . Accordingly, the speeds of the carriages are $ [6, 2, 1, 1] $ and will form $ 3 $ of the train. - After the second message the array $ a = [6, 2, 1, 0] $ . Accordingly, the speeds of the carriages are $ [6, 2, 1, 0] $ , and $ 4 $ of the train will be formed. For the second test case: - Initially, the array $ a = [10, 13, 5, 2, 6] $ . - After the first message, the array $ a = [10, 9, 5, 2, 6] $ . Accordingly, the speeds of the carriages are equal: $ [10, 9, 5, 2, 2] $ , and $ 4 $ of the train will be formed. - After the second message the array $ a = [10, 9, 5, 2, 4] $ . Accordingly, the speeds of the carriages are $ [10, 9, 5, 2, 2] $ , and $ 4 $ of the train will be formed. - After the third message the array $ a = [5, 9, 5, 2, 4] $ . Accordingly, the speeds of the carriages are $ [5, 5, 5, 2, 2] $ , and $ 2 $ of the train will be formed. - After the fourth message the array $ a = [5, 9, 3, 2, 4] $ . Accordingly, the speeds of the carriages are $ [5, 5, 3, 2, 2] $ , and $ 3 $ of the train will be formed.

**题目大意**

在铁轨上有 $ n $ 节独立的车厢，从左到右编号为 $ 1 $ 到 $ n $。每节车厢都有自己的引擎，可以达到速度 $ a_i $ km/h，但速度不能超过前面的车厢。因此，所有车厢开始向左移动时，会自然形成若干节速度相同的连续车厢，称为“一节火车”。例如，对于数组 $ a = [10, 13, 5, 2, 6] $，最终速度将是 $ [10, 10, 5, 2, 2] $，形成 $ 3 $ 节火车。

接下来，会收到 $ m $ 条信息，每条信息形如 $ k\ d $，表示第 $ k $ 节车厢的最高速度因引擎老化而下降 $ d $（即 $ a_k = a_k - d $）。消息按顺序到达，处理下一条消息时需考虑之前所有消息的影响。

在每条信息后，确定形成的火车节数。

**输入格式**

输入的第一行为测试用例数 $ t $。每个测试用例的第一行是空的，第二行包含两个整数 $ n $ 和 $ m $，第三行包含序列 $ \{a_i\}_{i=1}^n $，接下来 $ m $ 行每行给出一条信息 $ k_i\ d_i $。

**输出格式**

输出 $ t $ 行，每行对应一个测试用例，每行用空格分隔 $ m $ 个整数，表示收到每条信息后的火车节数。

**数据范围**

- $ t \in [1,10^4]; $
- $ n, m \in [1,10^5]; $
- $ a_i \in [0,10^9] $ 对于所有 $ i \in [1,n]; $
- $ k_j \in [1,n],\ d_j \in [0,a_{k_j}] $ 对于所有 $ j \in [1,m]; $
- 所有测试用例的 $ n $ 的总和及 $ m $ 的总和均不超过 $ 10^5 $。

**输入输出样例**

输入样例 #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
```
**题目大意** 在铁轨上有 $ n $ 节独立的车厢，从左到右编号为 $ 1 $ 到 $ n $。每节车厢都有自己的引擎，可以达到速度 $ a_i $ km/h，但速度不能超过前面的车厢。因此，所有车厢开始向左移动时，会自然形成若干节速度相同的连续车厢，称为“一节火车”。例如，对于数组 $ a = [10, 13, 5, 2, 6] $，最终速度将是 $ [10, 10, 5, 2, 2] $，形成 $ 3 $ 节火车。 接下来，会收到 $ m $ 条信息，每条信息形如 $ k\ d $，表示第 $ k $ 节车厢的最高速度因引擎老化而下降 $ d $（即 $ a_k = a_k - d $）。消息按顺序到达，处理下一条消息时需考虑之前所有消息的影响。 在每条信息后，确定形成的火车节数。 **输入格式** 输入的第一行为测试用例数 $ t $。每个测试用例的第一行是空的，第二行包含两个整数 $ n $ 和 $ m $，第三行包含序列 $ \{a_i\}_{i=1}^n $，接下来 $ m $ 行每行给出一条信息 $ k_i\ d_i $。 **输出格式** 输出 $ t $ 行，每行对应一个测试用例，每行用空格分隔 $ m $ 个整数，表示收到每条信息后的火车节数。 **数据范围** - $ t \in [1,10^4]; $ - $ n, m \in [1,10^5]; $ - $ a_i \in [0,10^9] $ 对于所有 $ i \in [1,n]; $ - $ k_j \in [1,n],\ d_j \in [0,a_{k_j}] $ 对于所有 $ j \in [1,m]; $ - 所有测试用例的 $ n $ 的总和及 $ m $ 的总和均不超过 $ 10^5 $。 **输入输出样例** 输入样例 #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 ```