結果

問題 No.1234 典型RMQ
ユーザー だれだれ
提出日時 2021-03-29 05:20:57
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 628 ms / 2,000 ms
コード長 5,220 bytes
コンパイル時間 399 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 97,828 KB
最終ジャッジ日時 2024-11-09 02:45:12
合計ジャッジ時間 13,370 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

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