class Lazy_Evaluation_Tree(): def __init__(self,L,calc,unit,op,comp,id): """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 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=1): 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,index=1,left_closed=True,right_closed=True): 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,index=1): """ 第k要素をxに変更する. """ 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,index=1,left_closed=True,right_closed=True): 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 m