树模板：珂朵莉树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class ODT:
    def __init__(self,):
        from sortedcontainers import SortedList
        self.sl = SortedList()
    
    def update(self,l,r,x):
        s, e = l, r
        pos = self.sl.bisect_right((r+2,))-1
        while pos>=0 and self.sl[pos][1]>=l-1:
            a, b, y = self.sl.pop(pos)
            if y==x:
                s, e = min(s, a), max(e, b)
            else:
                if b>r:
                    self.sl.add((r+1,b,y))
                if a<l:
                    self.sl.add((a,l-1,y))
            pos -= 1
        self.sl.add((s, e, x))