動機

  1. 不要想著線段樹什麼的
  2. 魔鬼藏在細節中
  3. 謝謝花花醬
  4. 我應該要複習bsearch QQ

Problem

A Range Module is a module that tracks ranges of numbers. Design a data structure to track the ranges represented as half-open intervals and query about them.

A half-open interval [left, right) denotes all the real numbers x where left <= x < right.

Implement the RangeModule class:

  • RangeModule() Initializes the object of the data structure.
  • void addRange(int left, int right) Adds the half-open interval [left, right), tracking every real number in that interval. Adding an interval that partially overlaps with currently tracked numbers should add any numbers in the interval [left, right) that are not already tracked.
  • boolean queryRange(int left, int right) Returns true if every real number in the interval [left, right) is currently being tracked, and false otherwise.
  • void removeRange(int left, int right) Stops tracking every real number currently being tracked in the half-open interval [left, right).

 

Example 1:

Input["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"][[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]Output[Leetcode, null, null, true, false, true]ExplanationRangeModule rangeModule = new RangeModule();rangeModule.addRange(10, 20);rangeModule.removeRange(14, 16);rangeModule.queryRange(10, 14); // return True,(Every number in [10, 14) is being tracked)rangeModule.queryRange(13, 15); // return False,(Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)rangeModule.queryRange(16, 17); // return True, (The number 16 in [16, 17) is still being tracked, despite the remove operation)

 

Constraints:

  • 1 <= left < right <= 109
  • At most 104 calls will be made to addRange, queryRange, and removeRange.

sol

如果沒有花花醬，我解不出來 QQ

其實就是延續insert interval的思緒，我當初做insert interval是用mono stack去做…

但insert interval其實就是找出有overlap的range(左閉右開)之後整個幹掉(中間可能有很多interval)，之後重建

這裡挑overlap是有細節的!! 假設當前segments有[[1,10], [10,20]]，要加[10,30]，右邊的位置會是2，但左邊的位置不能是1!!

原本我挑overlap的方式是這樣

def findSeg(self, left, right):
  l, r = self.seg.bisect(left), self.seg.bisect(right)
  return [
      l-1 if l != 0 and self.seg[self.seg.iloc[l-1]] > left else l,
      r
  ]

也就是要seg完全包含left才算進去，但是這樣會產生剛剛提到的悲劇

所以要改成

def findSeg(self, left, right):
  l, r = self.seg.bisect(left), self.seg.bisect(right)
  return [
      l-1 if l != 0 and self.seg[self.seg.iloc[l-1]] >= left else l,
      r
  ]

但是這樣不是會包含到[1,10]，這不符合左閉右開的定義阿 如果說，每一次都是[a,x], [b,c] 但是 x = b這種狀態，這樣就okay，但每次都會這樣嗎?

有趣的是，會。 這個就是特別處理這個case的，剛好符合我們要的所有需求，所以okay

from sortedcontainers import SortedDict
class RangeModule:
    def __init__(self):
        self.seg = SortedDict()
    
    def findSeg(self, left, right):
        l, r = self.seg.bisect(left), self.seg.bisect(right)
        return [
            l-1 if l != 0 and self.seg[self.seg.iloc[l-1]] > left else l,
            r
        ]
    def removeSegRange(self, l, r):
        keys = [self.seg.iloc[i] for i in range(l,r)]
        #print(f'removeSegRange {self.seg} {keys} {l} {r}')
        [self.seg.pop(k) for k in keys]
                
    def addRange(self, left: int, right: int) -> None:
        l, r = self.findSeg(left, right)
        print(f'{self.seg} {l} {r}')
        if l != r:
            left = min(left, self.seg.peekitem(l)[0])
            right = max(right, self.seg.peekitem(r-1)[1])
            self.removeSegRange(l, r)
        self.seg[left] = right
        print(f'ADD {(left,right)} {self.seg} {l} {r}')

    def queryRange(self, left: int, right: int) -> bool:
        l, r = self.findSeg(left, right)
        #print(f'Q {(left,right)} {self.seg} {l} {r}')
        return l != r and self.seg.iloc[l] <= left and self.seg[self.seg.iloc[l]] >= right

    def removeRange(self, left: int, right: int) -> None:
        l, r = self.findSeg(left, right)
        if l != r:
            start = min(left, self.seg.peekitem(l)[0])
            end = max(right, self.seg.peekitem(r-1)[1])
            self.removeSegRange(l, r)
            if start < left:
                self.seg[start] = left
            if right < end:
                self.seg[right] = end
        #print(f'RM {(left,right)} {self.seg} {l} {r}')