LC 2972. 统计移除递增子数组的数目 II

https://leetcode.cn/problems/count-the-number-of-incremovable-subarrays-ii/

这题还有一个简单的版本，内容是完全相同，只不过数据量更小。这题的数据量是在 10^5 左右，所以大致就是需要 O(nlgn) 的算法了。

假设我们选择了 \(a[i..n]\) 的话，然后我们需要挑选 \(a[0..j]\) , 需要满足几个条件：

首先是两个选择子数组都必须递增
然后就是 \(a[j] < a[i]\) .
结果就是有多少个j满足这个条件了。

在处理的时候需要做一个预处理，大致知道那些j的位置是有递增的，并且记录 `a[j]` 的值。然后逆向处理，寻找有多少个 j 满足这个条件。最后还需要考虑完全递增的情况，对于这种情况会重复计算prefix，在最后的结果上需要减去 (n+1)

class Solution:
    def incremovableSubarrayCount(self, nums: List[int]) -> int:
        n = len(nums)
        inc = [0] * n
        inc[0] = 1
        for i in range(1, n):
            inc[i] = inc[i - 1] & (nums[i] > nums[i - 1])

        # empty set.
        ans = 1
        from sortedcontainers import SortedList
        sl = SortedList()
        for i in range(n):
            if inc[i]:
                sl.add(nums[i])
                # prefix set.
                ans += 1
        if inc[-1]:
            ans -= (n + 1)

        flag = 1
        for i in reversed(range(n)):
            flag = flag & (nums[i] < nums[i + 1] if (i + 1) < n else 1)
            if not flag:
                break
            if inc[i]:
                sl.remove(nums[i])
            size = sl.bisect_right(nums[i] - 1) + 1
            # print(sl, nums[i:], size)
            ans += size

        return ans