cf：G. Count the Trains【sortedset + bisect + 模拟维持严格递减序列】

分析

这道题每次都需要求当前速度下，严格递减序列的长度
如果我们每次分开求，就会超时
所以我们要根据每次更改来更新新得递减序列的长度

首先我们根据一开始的速度得到一开始严格递减序列（我们记录的是idx）
然后我们开始修改，如果当前修改使得比前一个记录idx的val要严格小，我们将当前修改的id放入sortedset中
怎么看前一个记录的idx呢，通过bisect_right(s, x) - 1得到即可~
当然如果当前idx在一开头的位置，直接加入即可

加入了之后，要进行后续不服务严格递减的idx的删除
首先我们找到当前加入的x的下一个位置bisect_right(s,x)
然后用双指针找到需要删除的范围l和r 只要满足当前idx的val不小于x对应的val就r++
最后cut掉s[l:r]即可

这里就是sortedset中砍掉后面不符合要求的一段，直接del即可

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)

总结

cf中不能用sortedcontainers所以不知道对不对
思路是对的
然后list一种快速输出是print(*list)
然后sortedset可以add discard 和del[i:j]一般就是这几个用法
因为py默认的set是无序就很恼火！