Cf:g. count the trains [sortedset + bisect + simulation maintaining strict decreasing sequence]

analysis

This problem needs to be solved at the current speed every time , Strictly decreasing the length of the sequence
If we ask each time separately , It will time out
So we need to update the length of the new decreasing sequence according to each change

First, we get a strictly decreasing sequence at the beginning according to the speed at the beginning （ What we record is idx）
Then we began to modify , If the current modification makes the previous record idx Of val Be strict and small , We will modify the current id Put in sortedset in
What do you think of the previous record idx Well , adopt bisect_right(s, x) - 1 Just get it ~
Of course, if at present idx At the beginning , Just join in

After joining , Follow up services that do not strictly decrease idx The deletion of
First, we find the currently joined x Next position of bisect_right(s,x)
Then use the double pointer to find the range to be deleted l and r As long as you meet the current idx Of val Not less than x Corresponding val Just r++
Last cut fall s[l:r] that will do

Here is the sortedset Cut out the following paragraph that does not meet the requirements , direct del that will do

ac code（maybe）

from bisect import bisect_left, bisect_right
from sortedcontainers import SortedSet

for _ in range(int(input())):
    #print('eg:')
    empty = input()
    n, m = list(map(int, input().split()))
    a = list(map(int, input().split()))

    s = SortedSet(list()) # store the head(idx) of every train
    for i in range(n):
        if not s or a[i] < a[s[-1]]: # keep decreasing
            s.add(i)

    #print(s)
    ans = []
    for i in range(m):
        x, k = n, m = list(map(int, input().split()))
        x -= 1 # start from 0
        a[x] -= k

        # find the id right before x in s
        idx = bisect_right(s, x) - 1
        #print(idx)

        # if x at the very beginning
        if idx == 0:
            s.add(x)
        # if a[x] less than a[idx], add it
        elif a[x] < a[idx]:
            s.add(x)

        # delete the following id which val >= a[x]
        # keep strictly decreasing
        #print(s)
        l = r = bisect_right(s, x)
        while True:
            #print(r)
            if r == len(s) or a[s[r]] < a[x]:
                break
            r += 1
        # delete sth
        #print(l, r)
        del s[l: r]
        # print len
        ans.append(len(s))
    print(*ans)

summary

cf You can't use sortedcontainers So I don't know if it's right
The idea is right
then list A quick output is print(*list)
then sortedset Sure add discard and del[i:j] These are the general usages
because py default set If it's disorder, it's annoying ！