class Segment_Tree(): """ このプログラム内は1-index """ def __init__(self,L,calc,unit,index): """calcを演算とするリストLのSegment Treeを作成 calc:演算(2変数関数,モノイド) unit:モノイドcalcの単位元 (xe=ex=xを満たすe) index:数列の第1要素のindex """ self.calc=calc self.unit=unit self.index=index N=len(L) d=max(1,(N-1).bit_length()) k=1<1: m>>=1 self.data[m]=self.calc(self.data[m<<1],self.data[m<<1|1]) def product(self,From,To,index=1,left_closed=True,right_closed=True): L=(From-index)+self.N+(not left_closed) R=(To-index)+self.N+(right_closed) vL=self.unit vR=self.unit while L>=1 R>>=1 return self.calc(vL,vR) def all_product(self): return self.data[1] def max_right(self,left,cond,index=1): """以下の2つをともに満たすxの1つを返す.\n (1) r=left or cond(data[left]*data[left+1]*...*d[right-1]):True (2) r=N+index or cond(data[left]*data[left+1]*...*data[right]):False ※condが単調減少の時,cond(data[left]*...*data[right-1])を満たす最大のrightとなる. cond:関数(引数が同じならば結果も同じ) cond(unit):True index<=left<=r>=1 if not cond(calc(sm,self.data[left])): while left1 and right&1: right>>=1 if not cond(calc(self.data[right],sm)): while right