class SegTree: def __init__(self,op,e,v): self.n=len(v) self.op=op self.e=e self.size=1<<(self.n-1).bit_length() self.node=[self.e]*(2*self.size) for i in range(self.n): self.node[self.size+i]=v[i] for i in range(self.size-1,0,-1): self.node[i]=self.op(self.node[i*2],self.node[i*2+1]) def set(self,k,x): k+=self.size self.node[k]=x while k>1: k//=2 self.node[k]=self.op(self.node[2*k],self.node[2*k+1]) def prod_rec(self,a,b,k=1,l=0,r=-1): if r<0:r=self.size if (r<=a or b<=l):return self.e if (a<=l and r<=b):return self.node[k] vl=self.prod_rec(a,b,2*k,l,(l+r)//2) vr=self.prod_rec(a,b,2*k+1,(l+r)//2,r) return self.op(vl,vr) def prod(self,l,r): l,r=l+self.size,r+self.size vl,vr=self.e,self.e while l>=1 r>>=1 return self.op(vl,vr) def all_prod(self): return self.node[1] def get(self,k): return self.node[self.size+k] def max_right(self,l,f): if l==self.n:return self.n l+=self.size sm=self.e while True: while l&0:l>>=1 if not f(self.op(sm,self.node[l])): while l1 and r&1:r>>=1 if not f(self.op(self.node[r],sm)): while r