from math import sin,cos,atan2,sqrt,radians,pi class Segment_Tree(): def __init__(self,L,calc,unit): """calcを演算とするリストLのSegment Treeを作成 calc:演算(2変数関数,モノイド) unit:モノイドcalcの単位元 (xe=ex=xを満たすe) """ self.calc=calc self.unit=unit N=len(L) d=max(1,(N-1).bit_length()) k=2**d X=[unit]*(k-1)+L+[unit]*(k-len(L)) self.num=k self.depth=d for i in range(k-2,-1,-1): X[i]=calc(X[2*i+1],X[2*i+2]) self.data=X def get(self,k,index=0): return self.data[(self.num-1)+(k-index)] def update(self,k,x,index=0): """第k要素をxに変え,更新を行う. k:数列の要素 x:更新後の値 """ m=(self.num-1)+(k-index) self.data[m]=x for _ in range(self.depth): m=(m-1)//2 self.data[m]=self.calc(self.data[2*m+1],self.data[2*m+2]) def product(self,From,To,index=0,left_closed=True,right_closed=True): A=From-index+(not left_closed) B=To-index-(not right_closed) return self.__product_second(A,B+1,0,0,self.num) def __product_second(self,a,b,k,l,r): if r<=a or b<=l: return self.unit elif a<=l and r<=b: return self.data[k] else: alpha=self.__product_second(a,b,2*k+1,l,(l+r)//2) beta=self.__product_second(a,b,2*k+2,(l+r)//2,r) return self.calc(alpha,beta) def all_prod(self): return self.data[0] def max_right(self,l,r,cond,index=0): """以下の2つをともに満たすxの1つを返す.\n (1) r=l or cond(data[l]*data[l+1]*...*d[r-1]):True (2) r=x or cond(data[l]*data[l+1]*...*data[r]):False ※fが単調減少の時,cond(data[l]*...*data[r-1])を満たす最大のrとなる. cond:関数(引数が同じならば結果も同じ) cond(unit):True 0<=l<=r<=n """ l-=index assert 0<=l<=r<=self.num,"添字が範囲外" assert cond(self.unit),"単位元が条件を満たさない." if l==r: return r+index l+=(self.num-1) sm=self.unit calc=self.calc while True: while l%2: l=(l-1)>>1 if not cond(calc(sm,self.data[l])): while l