求区间最值
import sys
sys.setrecursionlimit(1000000)
class Node:
__slots__ = ["left", "right", "val", "tag"]
def __init__(self, left=None, right=None, val=0, tag=0):
self.left = left
self.right = right
self.val = val
self.tag = tag
class Tree:
def __init__(self):
self.root = Node()
def push_down(self, node):
if not node.left:
node.left = Node()
if not node.right:
node.right = Node()
if node.tag == 0:
return
node.left.val = node.left.tag = node.tag
node.right.val = node.right.tag = node.tag
node.tag = 0
def push_up(self, node):
node.val = max(node.left.val, node.right.val)
def update(self, node, l, r, ql, qr, val):
if ql <= l and qr >= r:
node.val = val
node.tag = val
return
self.push_down(node)
mid = l + r >> 1
if ql <= mid:
self.update(node.left, l, mid, ql, qr, val)
if qr > mid:
self.update(node.right, mid + 1, r, ql, qr, val)
self.push_up(node)
def query(self, node, l, r, ql, qr):
if ql <= l and qr >= r:
return node.val
self.push_down(node)
mid = l + r >> 1
ans = 0
if ql <= mid:
ans = self.query(node.left, l, mid, ql, qr)
if qr > mid:
ans = max(ans, self.query(node.right, mid + 1, r, ql, qr))
return ans
lst = [0, 1, 2, 3, 4, 5]
mytree = Tree()
n = len(lst)
MIN = 1
MAX = 100000
for i in range(1, n):
mytree.update(mytree.root, MIN, MAX, i, i, lst[i])
print(mytree.query(mytree.root, MIN, MAX, 1, 3))