class SegmentTree(object): def __init__(self,A,dot,e,comp,id,act): """ A: array of monoid (M,dot,e) comp: composite function of Hom(M), comp(f,g)=gf id: identity map of M act: action on (Hom(M),M), act(f,a)=f(a) """ n=2**((len(A)-1).bit_length()) self.__n=n self.__dot=dot self.__e=e self.__comp=comp self.__id=id self.__act=act self.__node=[e]*(2*n) self.__lazy=[id]*(2*n) for i in range(len(A)): self.__node[i+n]=A[i] for i in range(n-1,0,-1): self.__node[i]=self.__dot(self.__node[2*i],self.__node[2*i+1]) def __propagate(self,i): if(self.__lazy[i]==self.__id): return node=self.__node lazy=self.__lazy if(i