树状数组

求逆序对总数total，用树状数组即可求解

滑动窗口

滑动窗口 [l,r]，代表移除的区间。

建立两个树状数组left和right。

在滑动过程中，维护树状数组left和right，并维护逆序对总数total。

滑动过程中保证维护后的total >= k，即可统计可删除区间总数。

代码

# 树状数组
class NumArray:
    # 获取最低位1的位置
    def lowbit(self,x):
        return x & -x
    
    def __init__(self, nums):
        self.nums = nums
        self.tree = [0] * (len(nums)+1)
#         for index,num in enumerate(nums):
#             self.add(index+1,num)   
    
    # 添加值
    def add(self,index,value):       
        while index <= len(self.nums):
            self.tree[index] += value
            index += self.lowbit(index)   
    
    # 求前缀和
    def query(self,index):
        res = 0
        while index > 0:
            res += self.tree[index]
            index -= self.lowbit(index)
        return res


    def sumRange(self, left: int, right: int) -> int:  
        # 类似前缀和求中间区间值      
        return self.query(right) - self.query(left-1)
        



n,k = map(int,input().strip().split())
arr = list(map(int,input().strip().split()))

max_num = int(1e6+2)
left = NumArray([0]*max_num)
right = NumArray([0]*max_num)

total = 0
for num in arr:
    total += right.sumRange(num+1,max_num-1)
    right.add(num,1)

l,r = 0,0

res = 0
# 一个区间都不删除
if total >= k:
    res += 1
    
while r < n:
    num = arr[r]
    right.add(num,-1)
    
    total -= right.sumRange(0,num-1)
    total -= left.sumRange(num+1,max_num-1)
    
    while l <= r and total < k:
        num = arr[l]
        total += right.sumRange(0,num-1)
        total += left.sumRange(num+1,max_num-1)
        left.add(num,1)
        l += 1
    
    res += r - l + 1
    r += 1


print(res)