結果

問題 No.1234 典型RMQ
ユーザー だれだれ
提出日時 2021-03-29 05:20:57
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 612 ms / 2,000 ms
コード長 5,220 bytes
コンパイル時間 269 ms
コンパイル使用メモリ 82,236 KB
実行使用メモリ 98,040 KB
最終ジャッジ日時 2024-04-26 11:52:23
合計ジャッジ時間 13,047 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
53,376 KB
testcase_01 AC 41 ms
53,632 KB
testcase_02 AC 41 ms
53,120 KB
testcase_03 AC 41 ms
52,992 KB
testcase_04 AC 40 ms
53,120 KB
testcase_05 AC 41 ms
53,248 KB
testcase_06 AC 585 ms
95,288 KB
testcase_07 AC 463 ms
88,228 KB
testcase_08 AC 611 ms
97,584 KB
testcase_09 AC 542 ms
93,616 KB
testcase_10 AC 612 ms
95,724 KB
testcase_11 AC 561 ms
95,964 KB
testcase_12 AC 507 ms
92,632 KB
testcase_13 AC 470 ms
89,276 KB
testcase_14 AC 532 ms
92,316 KB
testcase_15 AC 482 ms
91,712 KB
testcase_16 AC 576 ms
96,660 KB
testcase_17 AC 520 ms
91,752 KB
testcase_18 AC 399 ms
86,428 KB
testcase_19 AC 598 ms
97,828 KB
testcase_20 AC 290 ms
93,688 KB
testcase_21 AC 553 ms
95,400 KB
testcase_22 AC 386 ms
96,080 KB
testcase_23 AC 382 ms
98,040 KB
testcase_24 AC 385 ms
97,960 KB
testcase_25 AC 379 ms
96,000 KB
testcase_26 AC 367 ms
96,128 KB
testcase_27 AC 40 ms
52,992 KB
testcase_28 AC 41 ms
53,376 KB
testcase_29 AC 40 ms
53,504 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class LazySegTree:
    def __init__(self, array, f, g, h, merge_id, comp_id):
        
        #self.height = (len(array) - 1).bit_length()
        #self.n = 1 << self.height

        self.n = len(array)

        self.merge_id = merge_id
        self.comp_id = comp_id

        self.tree = [self.merge_id] * (self.n << 1)
        self.lazy = [self.comp_id] * (self.n << 1)

        self.merge = f
        self.mapping = g
        self.composition = h

        for i in range(len(array)):
            self.tree[self.n + i] = array[i]

        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.merge (self.tree[i << 1], self.tree[i << 1 | 1])


    def eval_at(self, i):
        return self.mapping(self.lazy[i], self.tree[i])


    def prog_at(self, i):
        x = self.lazy[i]
        if x == self.comp_id: return

        self.tree[i] = self.mapping(x, self.tree[i])
        self.lazy[i] = self.comp_id

        if i < self.n:
            i <<= 1
            self.lazy[i] = self.composition(x, self.lazy[i])
            self.lazy[i | 1] = self.composition(x, self.lazy[i | 1])


    def prog_down(self, i):
        x = i.bit_length() - 1
        for j in range(x, 0, -1):
            self.prog_at(i >> j)


    def merge_up(self, i):
        while i > 1:
            i >>= 1
            self.tree[i] = self.merge(self.eval_at(i << 1), self.eval_at(i << 1 | 1))


    def range_update(self, l, r, x):
        l += self.n
        r += self.n

        lm = l // (l & -l)
        rm = r // (r & -r) - 1

        self.prog_down(lm)
        self.prog_down(rm)

        while l < r:
            if r & 1:
                r -= 1
                self.lazy[r] = self.composition(x, self.lazy[r])

            if l & 1:
                self.lazy[l] = self.composition(x, self.lazy[l])
                l += 1

            l >>= 1
            r >>= 1

        self.merge_up(lm)
        self.merge_up(rm)


    def get(self, i):
        i += self.n
        self.prog_down(i)
        return self.eval_at(i)


    def update(self, i, x):
        i += self.n
        self.prog_down(i)
        self.tree[i] = x
        self.lazy[i] = self.comp_id
        self.merge_up(i)


    def query(self, l, r):
        l += self.n
        r += self.n

        self.prog_down(l // (l & -l))
        self.prog_down(r // (r & -r) - 1)

        lf, rf = self.merge_id, self.merge_id

        while l < r:
            if r & 1:
                r -= 1
                rf = self.merge(self.eval_at(r), rf)

            if l & 1:
                lf = self.merge(lf, self.eval_at(l))
                l += 1

            l >>= 1
            r >>= 1

        return self.merge(lf, rf)


    def query_all(self):
        return self.eval_at(1)


    def min_left(self, l, r, f, sss):
        nr = r
        l += self.n
        r += self.n

        self.prog_down(l // (l & -l))
        self.prog_down(r // (r & -r) - 1)

        lv, rv = [], []

        while l < r:
            if l & 1:
                lv.append(l)
                l += 1
            if r & 1:
                r -= 1
                rv.append(r)
            l >>= 1
            r >>= 1

        now = self.merge_id

        for i in lv + rv[::-1]:
            if f(self.merge(now, self.eval_at(i)), sss):
                while True:
                    if f(self.merge(now, self.eval_at(i)), sss):
                        if i >= self.n:
                            return i - self.n
                        else:
                            self.prog_at(i)
                            i <<= 1
                    else:
                        now = self.merge(now, self.eval_at(i))
                        i += 1
            else:
                now = self.merge(now, self.eval_at(i))

        return nr + 1


    def max_right(self, l, r, f, sss):
        nl = l
        l += self.n
        r += self.n

        self.prog_down(l // (l & -l))
        self.prog_down(r // (r & -r) - 1)

        lv, rv = [], []

        while l < r:
            if l & 1:
                lv.append(l)
                l += 1
            if r & 1:
                r -= 1
                rv.append(r)
            l >>= 1
            r >>= 1

        now = self.merge_id

        for i in rv + lv[::-1]:
            if f(self.merge(self.eval_at(i), now), sss):
                while True:
                    if f(self.merge(self.eval_at(i), now), sss):
                        if i >= self.n:
                            return i - self.n + 1
                        else:
                            self.prog_at(i)
                            i <<= 1
                            i += 1
                    else:
                        now = self.merge(self.eval_at(i), now)
                        i -= 1
            else:
                now = self.merge(self.eval_at(i), now)

        return nl


import sys
input=sys.stdin.readline

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

def f(a, b):
    return a + b

S = LazySegTree(a, min, f, f, 1e18, 0)

ans = []

q = int(input())
for _ in range(q):
    k, l, r, c = map(int, input().split())
    l -= 1
    if k == 1:
        S.range_update(l, r, c)
    else:
        ans.append(S.query(l, r))

if ans:
    print(*ans, sep = "\n")
0