結果

問題 No.1234 典型RMQ
ユーザー shotoyooshotoyoo
提出日時 2020-09-19 02:25:09
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 879 ms / 2,000 ms
コード長 3,375 bytes
コンパイル時間 368 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 102,656 KB
最終ジャッジ日時 2024-11-09 02:07:20
合計ジャッジ時間 18,192 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 45 ms
52,480 KB
testcase_01 AC 44 ms
52,736 KB
testcase_02 AC 44 ms
52,992 KB
testcase_03 AC 44 ms
52,992 KB
testcase_04 AC 44 ms
52,480 KB
testcase_05 AC 43 ms
52,608 KB
testcase_06 AC 843 ms
98,816 KB
testcase_07 AC 613 ms
83,712 KB
testcase_08 AC 866 ms
102,656 KB
testcase_09 AC 813 ms
94,080 KB
testcase_10 AC 854 ms
99,840 KB
testcase_11 AC 829 ms
99,072 KB
testcase_12 AC 756 ms
91,904 KB
testcase_13 AC 615 ms
83,840 KB
testcase_14 AC 864 ms
93,568 KB
testcase_15 AC 722 ms
91,264 KB
testcase_16 AC 879 ms
99,584 KB
testcase_17 AC 769 ms
92,032 KB
testcase_18 AC 524 ms
81,280 KB
testcase_19 AC 869 ms
102,528 KB
testcase_20 AC 435 ms
100,224 KB
testcase_21 AC 821 ms
98,560 KB
testcase_22 AC 567 ms
101,888 KB
testcase_23 AC 606 ms
102,016 KB
testcase_24 AC 537 ms
101,888 KB
testcase_25 AC 556 ms
101,888 KB
testcase_26 AC 542 ms
102,144 KB
testcase_27 AC 43 ms
52,608 KB
testcase_28 AC 44 ms
52,736 KB
testcase_29 AC 44 ms
52,992 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


### 遅延評価セグメント木
class LazySegmentTree:
    def __init__(self, n, a=None):
        """初期化
        num : n以上の最小の2のべき乗
        """
        num = 1
        while num<=n:
            num *= 2
        self.num = num
        self.seg = [ninf] * (2*self.num-1)
        self.lazy = [f0] * (2*self.num-1)
        self.ls = [0]*(2*self.num-1)
        self.rs = [0]*(2*self.num-1)
        self.ls[0] = 0
        self.rs[0] = self.num
        for i in range(self.num-1):
            self.ls[2*i+1] = self.ls[i]
            self.rs[2*i+1] = (self.ls[i] + self.rs[i])//2
            self.ls[2*i+2] = (self.ls[i] + self.rs[i])//2
            self.rs[2*i+2] = self.rs[i]
        if a is not None:
            # O(n)で初期化
            assert len(a)==n
            for i in range(n):
                self.seg[num-1+i] = a[i]
            for k in range(num-2, -1, -1):
                self.seg[k] = op(self.seg[2*k+1], self.seg[2*k+2])
    def eval(self, k):
        if self.lazy[k]==f0:
            return 
        if k<self.num-1:
            self.lazy[k*2+1] = composition(self.lazy[k], self.lazy[k*2+1])
            self.lazy[k*2+2] = composition(self.lazy[k], self.lazy[k*2+2])
        self.seg[k] = mapping(self.lazy[k], self.seg[k])
        self.lazy[k] = f0
    def eval_all(self):
        for i in range(2*self.num-1):
            self.eval(i)
    def update(self,a,b,x=None,f=None):
        """A[a]...A[b-1]をxに更新する
        """
        if f is None:
            # 更新クエリ
            f = lambda y: x
        k = 0
        q = [k] # k>=0なら行きがけ順
        # 重なる区間を深さ優先探索
        while q:
            k = q.pop()
            l,r = self.ls[k], self.rs[k]
            if k>=0:
                self.eval(k)
                if r<=a or b<=l:
                    continue
                elif a<=l and r<=b:
                    self.lazy[k] = composition(f, self.lazy[k])
                    self.eval(k)
                else:
                    q.append(~k)
                    q.append(2*k+1)
                    q.append(2*k+2)
            else:
                k = ~k
                self.seg[k] = op(self.seg[2*k+1], self.seg[2*k+2])
    def query(self,a,b):
        k = 0
        l = 0
        r = self.num
        q = [k]
        ans = ninf
        # 重なる区間を深さ優先探索
        while q:
            k = q.pop()
            l,r = self.ls[k], self.rs[k]
            self.eval(k)
            if r<=a or b<=l:
                continue
            elif a<=l and r<=b:
                ans = op(ans, self.seg[k])
            else:
                q.append(2*k+2)
                q.append(2*k+1)
#             print(q, ans, l,r,a,b, self.seg[k])
        return ans
n = int(input())
a = list(map(int, input().split()))
q = int(input())
# ninf = -10**9
# op = max
# mapping = lambda f,x: f(x)
# composition = lambda f1, f2: f1 if f1 is not None else f2
ninf = 10**20
op = lambda x,y: min(x,y)
mapping = lambda f,x: f+x
composition = lambda f1, f2: f1+f2
f0 = 0
sg = LazySegmentTree(n, a)
for _ in range(q):
    k,l,r,c = map(int, input().split())
    if k==1:
        sg.update(l-1,r,f=c)
    else:
        print(sg.query(l-1,r))
0