Number of minimum on a segments

Правка en1, от aviiiii2130, 2026-06-01 17:40:43

n , m = map(int , input().split()) nums = list(map(int , input().split()))

ST = [float("inf") for _ in range(4*n)]

def build(node , l , r): global nums , ST if l == r: ST[node] = [nums[l],1] else: mid = l + (r-l)//2 build(2*node , l , mid) build(2*node +1 , mid+1 , r) if ST[2*node][0] < ST[2*node + 1][0]: ST[node] = ST[2*node] elif ST[2*node][0] > ST[2*node + 1][0]:
ST[node] = ST[2*node + 1] else: ST[node] = [ST[2*node][0] , ST[2*node][1] + ST[2*node + 1][1]]

build(1 , 0 , n-1)
def update(node , l , r , ind , val): global nums , ST if l == r: nums[ind] = val ST[node] = [val,1] else: mid = l + (r-l)//2 if l <= ind and ind <= mid: update(2*node , l , mid , ind , val) else: update(2*node+1 , mid+1 , r ,ind , val) if ST[2*node][0] < ST[2*node + 1][0]: ST[node] = ST[2*node] elif ST[2*node][0] > ST[2*node + 1][0]:
ST[node] = ST[2*node + 1] else: ST[node] = [ST[2*node][0] , ST[2*node][1] + ST[2*node + 1][1]]

def query(node , l , r , ql ,qr): global nums , ST if qr < l or ql > r: return [float("inf"), 0] if l <= ql and r <= qr: return ST[node] mid = l+(r-l)//2 left = query(2*node , l , mid , ql ,qr) right = query(2*node+1 , mid+1 , r , ql ,qr) if left[0] < right[0]: return left elif right[0] < left[0]: return right else: return [left[0] , left[1] + right[1]]

for _ in range(m): ch , x , y = map(int , input().split()) if ch == 1: update(1 , 0 , n-1 , x , y) if ch == 2: res = query(1 , 0 , n-1 , x , y-1) print(res[0] , res[1])

I don't know whats wrong with my code :(

Теги segment tree, itmo academy, pilot couse

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский aviiiii2130 2026-06-01 17:44:02 79
en1 Английский aviiiii2130 2026-06-01 17:40:43 1977 Initial revision (published)