Problem: 3510. 移除最小数对使数组有序 II

[TOC]

思路

区间合并 + 堆

先不管是否为递增数组，当作一道新题目，每次操作选择相邻的最小和。然后合并

要获取最小的相邻值，那就用最小堆，两个相邻值合并相当于区间合并，用area来模拟区间合并：

        # 区间合并后，当前 i 的区间范围，-inf 即为被合并了
        area = [ (i,i) for i in range(n) ]

并初始化堆，堆中包含三个值：

• 合并后的和
• 第一个区间的左端点
• 第二个区间的左端点)

        for i in range(n-1):
            heappush(heap,(nums[i]+nums[i+1],i,i+1))

模拟合并的代码：

        while True:
            while heap:
                num,l,r = heap[0]
                
                if area[l][1] + 1 != r or nums[l] + nums[r] != num:
                    heappop(heap)
                else:
                    break
            # 合并完了
            if not heap:
                break

            # 操作
            num,l,r = heappop(heap)
            
            # 两个区间
            a,b = area[l]
            x,y = area[r]
            
            # 求和合并
            nums[a] = num
            nums[y] = num
            
            # 区间合并
            area[b] = area[x] = (-inf,-inf)
            area[a] = (a,y)
            area[y] = (a,y)

            # 和前后区间合并并入堆
            if y + 1 < n and area[y+1][0] != -inf:
                heappush(heap,(num + nums[y+1],l,y+1))

            if a - 1 >= 0 and area[a-1][0] != -inf:
                heappush(heap,(num + nums[area[a-1][0]],area[a-1][0],l))

线段树

现在考虑判断每次操作后，合并后的数组是否递增：

• 区间修改: 区间合并可以看作把两个区间中的所有值都改成合并后的值
• 区间查询：查询整个数组是否递增

看到区间修改和区间查询，应该要想到线段树了

一般出现区间修改都考虑lazy线段树，但这题不需要，因为每次被合并的区间都不会再对该区间中的子区间进行操作，也就是不会有lazy标记下放了，所以不需要lazy标记

f[k]

f[k] 中维护三个值：

        # 真实值，是否递增，区间左侧值，区间右侧值
        self.f = [[False,-1,-1] for _ in range(4*n)]

pushup 函数

这个合并不难：

    def pushup(self,lp,rp):
        lf,a,b = lp
        rf,x,y = rp
        if not lf or not rf:
            return (False,-1,-1)

        if b <= x:
            return (True,a,y)
        else:
            return (False,-1,-1)

最后就是在第一步模拟操作时加入 区间修改和区间查询 ，以及操作数统计就好了。

更多题目模板总结，请参考2024年度总结与题目分享

Code

###Python3

# 标记不下放版本
class SegmentTree:
    def __init__(self,nums):
        n = len(nums)
        self.nums = nums
        
        # 真实值，是否递增，区间左侧值，区间右侧值
        self.f = [[False,-1,-1] for _ in range(4*n)]
        
        self.buildTree(1,0,n-1)
        self.n = n

    def pushup(self,lp,rp):
        lf,a,b = lp
        rf,x,y = rp
        if not lf or not rf:
            return (False,-1,-1)

        if b <= x:
            return (True,a,y)
        else:
            return (False,-1,-1)
    
    # 初始化，求区间和
    def buildTree(self,k,l,r):
        # 叶子节点
        if l == r:
            self.f[k] = (True,self.nums[l],self.nums[l])
            return 
        mid = (l+r)//2
        self.buildTree(2*k,l,mid)
        self.buildTree(2*k+1,mid+1,r)
        
        # 每个k掌管 [2*k,2*k+1]
        self.f[k] = self.pushup(self.f[2*k],self.f[2*k+1])
    
    def update(self,start,end,x):
        return self._update(1,0,self.n-1,start,end,x)
    
    def _update(self,k,l,r,start,end,x):
        # 序号为k的点，掌管范围是l～r， 在区间start～end上，
        # 待更新区间刚好等于当前标准区间，则直接更新
        if l == start and r == end:
            # 肯定递增
            self.f[k] = [True,x,x]
            return
        
        mid = (l+r)//2
            
        if end <= mid: # 只在左子树
            self._update(2*k,l,mid,start,end,x)
             # 注意这里的return
        elif start > mid: # 只在右子树
            self._update(2*k+1,mid+1,r,start,end,x)
        else:
            # 否则对左右子树都需要处理
            self._update(2*k,  l,   mid,   start,mid,x)
            self._update(2*k+1,mid+1,r,    mid+1,end,x) 
        
        # 后缀数组更新，左右子树更新后更新当前子树
        self.f[k] = self.pushup(self.f[2*k],self.f[2*k+1])
    
    def query(self):
        return self.f[1][0]
    
    # 范围内含有1的个数
    def _query(self,k,l,r,start,end):
        # update时对于标准区间已经更新，返回即可
        if l == start and r == end: # 叶子节点
            return self.f[k]
        
        mid = (l+r)//2
        
        # 需要更新，标记下放
        if not self.v[k]:
            self._update(2*k,l,mid,l,mid)
            self._update(2*k+1,mid+1,r,mid+1,r)
            self.v[k] = True
        
        if end <= mid:
            return self._query(2*k,l,mid,start,end) # 注意这里的p已经加上了v[k]的影响
        elif start > mid:
            return self._query(2*k+1,mid+1,r,start,end) 
        
        leftPart = self._query(2*k,l,mid,start,mid)
        rightPart = self._query(2*k+1,mid+1,r,mid+1,end)
        return leftPart + rightPart


class Solution:
    def minimumPairRemoval(self, nums: List[int]) -> int:
        '''
        相邻和最小的 a,b
        a = a + b
        移除b
        非递减
        1e5
        线段树
        nums[i] nums[j] 合并的话
        相当于
        区间修改 把区间 [i,j] 换成相同的值为 nums[i] + nums[j]
        区间查询 查询整个区间是否递增
        那就是线段树

        快速找最小：
        堆 + 并查集模拟删除
        '''
        n = len(nums)
        # 值，区间 [l,r] 两端点相加
        heap = []

        # 区间合并后，当前 i 的区间范围，-inf 即为被合并了
        area = [ (i,i) for i in range(n) ]
        for i in range(n-1):
            heappush(heap,(nums[i]+nums[i+1],i,i+1))
            
        tree = SegmentTree(nums)
        
        res = 0
        while not tree.query():
            res += 1
            while heap:
                num,l,r = heap[0]
                
                if area[l][1] + 1 != r or nums[l] + nums[r] != num:
                    heappop(heap)
                else:
                    break

            # 操作
            num,l,r = heappop(heap)
            
            # 两个区间
            a,b = area[l]
            x,y = area[r]
            
            # 求和合并
            nums[a] = num
            nums[y] = num
            tree.update(a,y,num)

            
            # 区间合并
            area[b] = area[x] = (-inf,-inf)
            area[a] = (a,y)
            area[y] = (a,y)

            # 和前后区间合并并入堆
            if y + 1 < n and area[y+1][0] != -inf:
                heappush(heap,(num + nums[y+1],l,y+1))

            if a - 1 >= 0 and area[a-1][0] != -inf:
                heappush(heap,(num + nums[area[a-1][0]],area[a-1][0],l))
                
        return res