結果

問題 No.1234 典型RMQ
ユーザー chineristACchineristAC
提出日時 2020-09-18 21:47:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 394 ms / 2,000 ms
コード長 2,795 bytes
コンパイル時間 276 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 94,592 KB
最終ジャッジ日時 2024-11-09 01:47:19
合計ジャッジ時間 10,169 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
52,864 KB
testcase_01 AC 38 ms
52,480 KB
testcase_02 AC 38 ms
52,736 KB
testcase_03 AC 38 ms
52,992 KB
testcase_04 AC 38 ms
52,864 KB
testcase_05 AC 38 ms
52,480 KB
testcase_06 AC 378 ms
89,832 KB
testcase_07 AC 335 ms
79,288 KB
testcase_08 AC 394 ms
94,208 KB
testcase_09 AC 369 ms
84,136 KB
testcase_10 AC 393 ms
92,292 KB
testcase_11 AC 386 ms
89,680 KB
testcase_12 AC 361 ms
83,504 KB
testcase_13 AC 354 ms
79,328 KB
testcase_14 AC 364 ms
83,336 KB
testcase_15 AC 363 ms
82,556 KB
testcase_16 AC 386 ms
92,152 KB
testcase_17 AC 373 ms
83,508 KB
testcase_18 AC 319 ms
78,748 KB
testcase_19 AC 393 ms
94,080 KB
testcase_20 AC 235 ms
93,440 KB
testcase_21 AC 379 ms
89,344 KB
testcase_22 AC 347 ms
94,464 KB
testcase_23 AC 350 ms
94,464 KB
testcase_24 AC 349 ms
94,464 KB
testcase_25 AC 348 ms
94,464 KB
testcase_26 AC 339 ms
94,592 KB
testcase_27 AC 37 ms
52,736 KB
testcase_28 AC 38 ms
52,608 KB
testcase_29 AC 37 ms
52,480 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class LazySegmentTree():
    __slots__ = ["merge","merge_unit","operate","merge_operate","operate_unit","n","data","lazy"]
    def __init__(self,n,init,merge,merge_unit,operate,merge_operate,operate_unit):
        self.merge=merge
        self.merge_unit=merge_unit
        self.operate=operate
        self.merge_operate=merge_operate
        self.operate_unit=operate_unit

        self.n=(n-1).bit_length()
        self.data=[merge_unit for i in range(1<<(self.n+1))]
        self.lazy=[operate_unit for i in range(1<<(self.n+1))]
        if init:
            for i in range(n):
                self.data[2**self.n+i]=init[i]
            for i in range(2**self.n-1,0,-1):
                self.data[i]=self.merge(self.data[2*i],self.data[2*i+1])

    def propagate(self,v):
        ope = self.lazy[v]
        if ope == self.operate_unit:
            return
        self.lazy[v]=self.operate_unit
        self.data[(v<<1)]=self.operate(self.data[(v<<1)],ope)
        self.data[(v<<1)+1]=self.operate(self.data[(v<<1)+1],ope)
        self.lazy[v<<1]=self.merge_operate(self.lazy[(v<<1)],ope)
        self.lazy[(v<<1)+1]=self.merge_operate(self.lazy[(v<<1)+1],ope)

    def propagate_above(self,i):
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            self.propagate(v)

    def remerge_above(self,i):
        while i:
            c = self.merge(self.data[i],self.data[i^1])
            i>>=1
            self.data[i]=self.operate(c,self.lazy[i])

    def update(self,l,r,x):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1
        while l<r:
            if l&1:
                self.data[l]=self.operate(self.data[l],x)
                self.lazy[l]=self.merge_operate(self.lazy[l],x)
                l+=1
            if r&1:
                self.data[r-1]=self.operate(self.data[r-1],x)
                self.lazy[r-1]=self.merge_operate(self.lazy[r-1],x)
            l>>=1
            r>>=1
        self.remerge_above(l0)
        self.remerge_above(r0)

    def query(self,l,r):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1
        self.propagate_above(l0)
        self.propagate_above(r0)
        res=self.merge_unit
        while l<r:
            if l&1:
                res=self.merge(res,self.data[l])
                l+=1
            if r&1:
                res=self.merge(res,self.data[r-1])
            l>>=1
            r>>=1
        return res

import sys

input = sys.stdin.readline

N = int(input())
a = list(map(int,input().split()))

LST = LazySegmentTree(N,a,min,10**18,lambda x,y:x+y,lambda x,y:x+y,0)

for _ in range(int(input())):
    k,l,r,c = map(int,input().split())
    l-=1
    if k==1:
        LST.update(l,r,c)
    else:
        print(LST.query(l,r))
0