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 :(
Auto comment: topic has been updated by aviiiii2130 (previous revision, new revision, compare).
i think you should change your build
ST[node] = ...to what you did in the update functionI did not understand what did you mean by change the build ?
Inside your query you have if l <= ql and r <= qr:
But it is l<=ql and qr<=r
when i changed the condition u just said i got this output for the test case given in the problem
As you can see it is wrong as the segment 0 to 2 must give 3 with frequency 2
sorry I mean ql<=l and r<=qr
Damm!! it worked thank you but i am still not sure how ql <= l and r<=qr works. We will retuen the segment which is completely inside the range [ql, qr] right but if we have l >= ql that might exceed ql right ?
We will retuen the segment which is completely inside the range [ql, qr] right Yes this is correct. Like if you have to query the range [4,11], and you are currently in the range [6,10] then you can directly return this range as it falls completly inside you query.
but if we have l >= ql that might exceed ql right ? I dont understand this question.
Also it is not an error this line if l <= ind and ind <= mid: in your update, but you can simply ignore the first condition I think. i.e. just if ind <= mid: