1.題目基本信息

1.1.題目描述

有一幅細長的畫，可以用數軸來表示。 給你一個長度為 n 、下標從 0 開始的二維整數數組 paint ，其中 paint[i] = [starti, endi] 表示在第 i 天你需要繪制 starti 和 endi 之間的區域。

多次繪制同一區域會導致不均勻，因此每個區域最多只能繪制 一次 。

返回一個長度為 n 的整數數組 worklog，其中 worklog[i] 是你在第 i 天繪制的 新 區域的數量。

1.2.題目地址

https://leetcode.cn/problems/amount-of-new-area-painted-each-day/description/

2.解題方法

2.1.解題思路

帶懶標記的線段樹 / 區間并查集

2.2.解題步驟

并查集思路：

將連續的區間放到同一個連通分量中，同時維護每個連通分量的根為區間最左側的結點

線段樹思路：

整體是一個求區間和的線段樹，主要區別在于每個結點的非0即1，lazy標記區間中元素是否全為0；然后使用區間和求出區間中被填充的位置個數，間接求出空閑的位置，即需要繪畫的區域長度

3.解題代碼

Python代碼【并查集版本】

class UnionFind():def __init__(self):self.roots = {}self.setCnt = 0self.rootSizes = {}def add(self, x:int) -> None:if x not in self.roots:self.roots[x] = xself.setCnt += 1self.rootSizes[x] = 1def find(self, x:int) -> int:if x not in self.roots:self.add(x)return xroot = self.roots[x]while root != self.roots[root]:root = self.roots[root]# 路徑壓縮while x != root:temp = self.roots[x]self.roots[x] = rootx = tempreturn rootdef union(self, x:int, y:int) -> None:rootx, rooty = self.find(x), self.find(y)if rootx != rooty:if rootx < rooty:self.roots[rooty] = rootxself.rootSizes[rootx] += self.rootSizes[rooty]else:self.roots[rootx] = rootyself.rootSizes[rooty] += self.rootSizes[rootx]self.setCnt -= 1class Solution:def amountPainted(self, paint: List[List[int]]) -> List[int]:# 思路1：并查集（每個數字為一個結點，根結點為連續區間的首部位置，所以每次union時都是將大根連接到小根上）uf = UnionFind()result = []for start, end in paint:thisCnt = 0rootStart, rootEnd = uf.find(start), uf.find(end)while rootEnd != rootStart:uf.union(rootEnd, rootEnd - 1)rootEnd = uf.find(rootEnd)thisCnt += 1result.append(thisCnt)return result

Python代碼【線段樹版本】

# ==> 帶懶標記 求范圍和 的線段樹（數組中的元素非0即1）
class SegmentTreeToSumWithLazy():def __init__(self, nums:list[int]):# 初始化線段樹的存儲數組并進行構建二叉平衡線段樹（這里采用平衡二叉樹，也可以用最大堆進行構建）self.n = len(nums)self.tree = [0] * (self.n * 4)   # 二叉平衡樹的范圍為4*n，如果使用最大堆的自底向上，則范圍2*n即可；維護區間和self.lazy = [0] * (self.n * 4)  # 懶標記數組，lazy[node]如果為1，表示node對應對應區間全部為1，反之不確定為多少self.build(nums, 0, 0, self.n - 1)# 基礎方法：構建樹，在node樹中，將nums[start:end+1]中的區間元素進行插入（node、start、end確定一個線段樹結點）def build(self, nums:list[int], node:int, start:int, end:int) -> None:if start == end:self.tree[node] = nums[start]return mid = (end - start) // 2 + start# 構建左子樹self.build(nums, node * 2 + 1, start, mid)# 構建右子樹self.build(nums, node * 2 + 2, mid + 1, end)# 和形式的線段樹；tree[node]記錄nums[start:end+1]之間元素的和self.tree[node] = self.tree[node * 2 + 1] + self.tree[node * 2 + 2]# 結點懶標記向下推送（基礎函數）：將node結點的懶標記推送到左右子結點中，并將自身的懶標記清空def pushDown(self, node:int, start:int, end:int) -> None:# 第一步，特殊判斷。node結點的懶標記值為0，無需向下推送，直接退出if self.lazy[node] == 0:return # 第二步，獲取左右結點的結點編號和范圍，更新左右結點的tree和lazy中的值mid = (end - start) // 2 + startleftChild = node * 2 + 1rightChild = node * 2 + 2self.tree[leftChild] = mid - start + 1self.lazy[leftChild] = 1self.tree[rightChild] = end - midself.lazy[rightChild] = 1# 第三步，清空node對應的lazy值self.lazy[node] = 0# 區間修改（基礎方法）：在結點node對應的[start,end]區間中，將其中[left,right]區間部分的原數組值全部增加valuedef rangeUpdate(self, value:int, left:int, right:int, node:int, start:int, end:int) -> None:# 第一步，遞歸退出條件# 1.1.node結點區間[start,end]和目標區間[left,right]不存在交集時，直接退出if left > end or right < start:return # 1.2.node結點區間[start,end]被目標區間[left,right]包含，直接更新lazy和tree數組。tree這種node結點對應值自增；在lazy數組中更新node結點的懶標記，lazy[node]自增valueif left <= start and right >= end:self.tree[node] = end - start + 1self.lazy[node] = 1return# 第二步，node區間和目標區間存在重疊的情況下，遞歸處理# 2.1.由于需要分到兩個子區間中進行遞歸操作，所以node對應的lazy值需要向下推送到子結點中；本質就是將node結點的lazy值分配到左右結點中，更新tree和lazy中對應的值self.pushDown(node, start, end)# 2.2.遞歸范圍更新兩個子樹leftChild, rightChild = node * 2 + 1, node * 2 + 2mid = (end - start) // 2 + startself.rangeUpdate(value, left, right, leftChild, start, mid)self.rangeUpdate(value, left, right, rightChild, mid + 1, end)# 第三步，更新當前結點的tree值（node中增加value的范圍不確定，所以通過子結點來更新）self.tree[node] = self.tree[leftChild] + self.tree[rightChild]# 單點修改：調用區間函數rangeUpdate進行def pointUpdate(self, index:int, value:int, node:int, start:int, end:int) -> None:self.rangeUpdate(value, index, index, node, start, end)# 區間查詢（基礎方法）：在結點node對應的[start,end]區間中，求[left,right]區間部分的原數組值的和def rangeSum(self, left:int, right:int, node:int, start:int, end:int) -> int:# 第一步，遞歸退出條件# 1.1.node結點區間和目標區間[left,right]不存在交集時，直接退出if left > end or right < start:return 0# 1.2.node結點區間被目標區間[left,right]包含，直接返回tree數組中node結點的值if left <= start and right >= end:return self.tree[node]# 第二步，node區間和目標區間存在重疊的情況下，遞歸處理# 2.1.由于需要分到兩個子區間中進行遞歸操作，所以node對應的lazy值需要向下推送到子結點中；本質就是將node結點的lazy值分配到左右結點中，更新tree和lazy中對應的值self.pushDown(node, start, end)# 2.2.遞歸獲取兩個子樹的范圍和，相加進行返回mid = (end - start) // 2 + startreturn self.rangeSum(left, right, node * 2 + 1, start, mid) + self.rangeSum(left, right, node * 2 + 2, mid + 1, end)class Solution:def amountPainted(self, paint: List[List[int]]) -> List[int]:# 思路2：帶懶標記的線段樹# 參考：Leetcode 307. 區域和檢索 - 數組可修改maxVal = max([b for a, b in paint])nums = [0] * (maxVal + 1)segTree = SegmentTreeToSumWithLazy(nums)result = []for start, end in paint:left, right = start, end - 1fullCnt = segTree.rangeSum(left, right, 0, 0, maxVal)result.append(right - left + 1 - fullCnt)segTree.rangeUpdate(0, left, right, 0, 0, maxVal)return result

4.執行結果