[Solution] Count the Trains Codeforces Solution

[Solution] Count the Trains Codeforces Solution

G. Count the Trains

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

There are n$n$ of independent carriages on the rails. The carriages are numbered from left to right from 1$1$ to n$n$. The carriages are not connected to each other. The carriages move to the left, so that the carriage with number 1$1$ moves ahead of all of them.

The i$i$-th carriage has its own engine, which can accelerate the carriage to ai$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$n=5$ carriages and array a=[10,13,5,2,6]$a=[10,13,5,2,6]$. Then the final speeds of the carriages will be [10,10,5,2,2]$[10,10,5,2,2]$. Respectively, 3$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$k$-th carriage has decreased by d$d$ (that is, there has been a change in the maximum speed of the carriage ak=ak−d$a_k=a_k-d$).

Messages arrive sequentially, the processing of the next message takes into account the changes from all previous messages.

Solution Click Below:-  CLICK HERE

After each message determine the number of formed trains.

Input

The first line of input data contains a single integer t$t$ (1≤t≤104$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$n$ and m$m$ (1≤n,m≤105$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$n$ integers: a1,a2,…,an$a_1,a_2,\dots ,a_n$ (0≤ai≤109$0\le a_i\le {10}^9$) — the number ai$a_i$ means that the carriage with number i$i$ can reach a speed of ai$a_i$ km/h.

The next m$m$ lines contain two integers kj$k_j$ and dj$d_j$ (1≤kj≤n$1\le k_j\le n$, 0≤dj≤akj$0\le d_j\le a_{k_j}$) —this is the message that the speed of the carriage with number kj$k_j$ has decreased by dj$d_j$. In other words, there has been a change in its maximum speed akj=akj−dj$a_{k_j}=a_{k_j}-d_j$. Note that at any time the speed of each carriage is non-negative. In other words, ai≥si$a_i\ge s_i$, where si$s_i$ —is the sum of such dj$d_j$ that kj=i$k_j=i$.

It is guaranteed that the sum of n$n$ over all test cases does not exceed 105${10}^5$. Similarly, it is guaranteed that the sum of m$m$ over all test cases does not exceed 105${10}^5$.

Output

Print t$t$ lines. On each line print the answer for the corresponding test case.

For each test case print m$m$ numbers: the number of trains formed after each message.