結果

問題 No.1234 典型RMQ
コンテスト
ユーザー 👑 Kazun
提出日時 2020-09-20 02:41:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,758 ms / 2,000 ms
コード長 3,395 bytes
コンパイル時間 308 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 120,348 KB
最終ジャッジ日時 2024-11-09 02:17:36
合計ジャッジ時間 32,412 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

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=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
        self.lazy=[self.id]*(2*k-1)

    def eval(self,k):
        if self.lazy[k]==self.id: #単位元だったら終了
            return

        if k<self.num-1: #葉でなければ子に伝搬
            self.lazy[2*k+1]=self.comp(self.lazy[k],self.lazy[2*k+1])
            self.lazy[2*k+2]=self.comp(self.lazy[k],self.lazy[2*k+2])

        #自身を更新(作用)
        self.data[k]=self.op(self.lazy[k],self.data[k])
        self.lazy[k]=self.id
        return

    def get(self,k,index=0):
        return self.product(k,k,index)

    def operate(self,From,To,alpha,index=0,left_closed=True,right_closed=True):
        A=From-index+(not left_closed)
        B=To-index-(not right_closed)

        return self.__operate_second(A,B+1,alpha,0,0,self.num)

    def __operate_second(self,a,b,alpha,k,l,r):
        self.eval(k)
        if (a<=l) and (r<=b): #完全に内側のとき
            self.lazy[k]=self.comp(alpha,self.lazy[k])
            self.eval(k)
        elif (a<r) and (l<b): #一部がかぶるとき
            self.__operate_second(a,b,alpha,2*k+1,l,(l+r)//2) #左の子
            self.__operate_second(a,b,alpha,2*k+2,(l+r)//2,r) #右の子
            self.data[k]=self.calc(self.data[2*k+1],self.data[2*k+2])

    def update(self,k,x):
        pass

    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):
        self.eval(k)
        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)
#================================================
N=int(input())
A=list(map(int,input().split()))

Q=int(input())

calc=lambda x,y:min(x,y)
unit=float("inf")
op=lambda a,x:a+x
comp=lambda a,b:a+b
id=0

S=Lazy_Evaluation_Tree(A,calc,unit,op,comp,id)

X=[]
for _ in range(Q):
    k,l,r,c=map(int,input().split())
    if k==1:
        S.operate(l,r,c,1)
    else:
        X.append(S.product(l,r,1))

print("\n".join(map(str,X)))
0