ODT

暴力美学，珂朵莉树！

from sortedcontainers import SortedList
class node:
    __slots__ = ['l', 'r', 'val']

    def __init__(self, l, r, val):
        self.l = l
        self.r = r
        self.val = val

    def __lt__(self, other):
        return self.l < other.l

    def unpack(self):
        return self.l,self.r,self.val

class Tree:
    def __init__(self,l,r,val):
        self.tree = SortedList([node(l,r,val)])

    def printf(self):
        for x in self.tree:
            l,r,val = x.unpack()
            print(f"[{l},{r},{val}]",end=' ')
        print()

    def split(self,pos):
        idx = self.tree.bisect_left(node(pos,0,0))
        if idx != len(self.tree) and self.tree[idx].l == pos:
            return idx
        idx -= 1
        l,r,val = self.tree[idx].unpack()
        self.tree[idx].r = pos - 1
        self.tree.add(node(pos,r,val))
        return idx + 1

    def get_split(self,l,r):
        return self.split(l),self.split(r + 1)

    # 将[l,r]区间赋值为val，所以要将与[l,r]区间有交集的区间给分隔开来
    def assign(self,l,r,val):
        left,right = self.get_split(l,r)
        del self.tree[left:right]
        self.tree.add(node(l,r,val))

    def update(self,l,r,val):
        left,right = self.get_split(l,r)
        for i in range(left,right):
            self.tree[i].val += val

    def query_min(self,l,r):
        left,right = self.get_split(l,r)
        return min(x.val for x in self.tree[left:right])

    def query_max(self,l,r):
        left,right = self.get_split(l,r)
        return max(x.val for x in self.tree[left:right])

    def query_kth(self,l,r,k):
        left,right = self.get_split(l,r)
        lst = [(x.val,x.r - x.l + 1) for x in self.tree[left:right]]
        for val,length in sorted(lst):
            k -= length
            if k <= 0:
                return val




mytree = Tree(1,10000,0)

mytree.update(1,100,1)

mytree.printf()

# [1,100,1] [101,10000,0]