class Segment_Tree: def __init__(self,N,f,e,lst=None,dynamic=False,bisect_search=True): self.f=f self.e=e self.N=N self.bisect_search=bisect_search if self.bisect_search: self.le=1 while self.le1: i>>= 1 self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1]) def Build(self,lst): for i,x in enumerate(lst,self.le): self.segment_tree[i]=x for i in range(self.le-1,0,-1): self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1]) def Fold(self,L=None,R=None): if L==None: L=self.le else: assert 0<=L<=self.N L+=self.le if R==None: R=self.le*2 else: assert 0<=R<=self.N R+=self.le vL=self.e vR=self.e while L>=1 R>>=1 return self.f(vL,vR) def Fold_Index(self,L=None,R=None): if L==None: L=self.le else: assert 0<=L<=self.N L+=self.le if R==None: R=self.le*2 else: assert 0<=R<=self.N R+=self.le if L==R: return None x=self.Fold(L-self.le,R-self.le) while L>=1 R>>=1 while i>=1 r>>=1 if f(self.f(vl,vr)): return self.N v=self.e while True: while L%2==0: L>>=1 vv=self.f(v,self.segment_tree[L]) if f(vv): v=vv L+=1 else: while L>=1 r>>=1 if f(self.f(vl,vr)): return 0 v=self.e while True: R-=1 while R>1 and R%2: R>>=1 vv=self.f(self.segment_tree[R],v) if f(vv): v=vv else: while R