class Lazy_Evaluation_Tree(): def __init__(self,L,calc,unit,op,comp,id,index): """calcを演算,opを作用とするリストLのSegment Treeを作成 calc:演算 unit:モノイドcalcの単位元 (xe=ex=xを満たすe) op:作用素 comp:作用素の合成 id:恒等写像 [条件] M:Monoid,F={f:F x M→ M:作用素}に対して,以下が成立する. Fは恒等写像 id を含む.つまり,任意の x in M に対して id(x)=x Fは写像の合成に閉じている.つまり,任意の f,g in F に対して, comp(f,g) in F 任意の f in F, x,y in M に対して,f(xy)=f(x)f(y)である. [注記] 作用素は左から掛ける.更新も左から. """ self.calc=calc self.unit=unit self.op=op self.comp=comp self.id=id self.index=index N=len(L) d=max(1,(N-1).bit_length()) k=1<>h) #配列の第m要素より上を全て再計算 def _recalc_above(self,m): while m>1: m>>=1 self.data[m]=self.calc( self._eval_at(m<<1), self._eval_at(m<<1|1) ) def get(self,k): index=self.index m=k-index+self.N self._propagate_above(m) self.data[m]=self._eval_at(m) self.lazy[m]=self.id return self.data[m] #作用 def operate(self,From,To,alpha,left_closed=True,right_closed=True): index=self.index L=(From-index)+self.N+(not left_closed) R=(To-index)+self.N+(right_closed) L0=R0=-1 X,Y=L,R-1 while X>=1 Y>>=1 L0=max(L0,X) R0=max(R0,Y) self._propagate_above(L0) self._propagate_above(R0) while L>=1 R>>=1 self._recalc_above(L0) self._recalc_above(R0) def update(self,k,x): """ 第k要素をxに変更する. """ index=self.index m=k-index+self.N self._propagate_above(m) self.data[m]=x self.lazy[m]=self.id self._recalc_above(m) def product(self,From,To,left_closed=True,right_closed=True): index=self.index L=(From-index)+self.N+(not left_closed) R=(To-index)+self.N+(right_closed) L0=R0=-1 X,Y=L,R-1 while X>=1 Y>>=1 L0=max(L0,X) R0=max(R0,Y) self._propagate_above(L0) self._propagate_above(R0) vL=vR=self.unit while L>=1 R>>=1 return self.calc(vL,vR) def all_product(self): return self.product(1,self.N,1) #リフレッシュ def refresh(self): for m in range(1,2*self.N): self.data[m]=self._eval_at(m) if m1: 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) x=left or cond(data[left]*data[left+1]*...*data[x-1]):True (2) x=N+index or cond(data[left]*data[left+1]*...*data[x]):False ※condが単調減少の時,cond(data[left]*...*data[x-1])を満たす最大のxとなる. 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