結果

問題 No.1099 Range Square Sum
ユーザー LyricalMaestroLyricalMaestro
提出日時 2024-01-08 00:02:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,440 ms / 2,000 ms
コード長 4,053 bytes
コンパイル時間 334 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 151,524 KB
最終ジャッジ日時 2024-09-27 19:33:16
合計ジャッジ時間 16,425 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
54,468 KB
testcase_01 AC 39 ms
53,680 KB
testcase_02 AC 39 ms
54,156 KB
testcase_03 AC 41 ms
53,944 KB
testcase_04 AC 40 ms
54,516 KB
testcase_05 AC 38 ms
53,184 KB
testcase_06 AC 39 ms
53,144 KB
testcase_07 AC 39 ms
53,948 KB
testcase_08 AC 40 ms
53,604 KB
testcase_09 AC 39 ms
53,848 KB
testcase_10 AC 40 ms
53,852 KB
testcase_11 AC 131 ms
77,536 KB
testcase_12 AC 129 ms
77,760 KB
testcase_13 AC 133 ms
77,964 KB
testcase_14 AC 131 ms
77,740 KB
testcase_15 AC 131 ms
77,500 KB
testcase_16 AC 132 ms
77,876 KB
testcase_17 AC 134 ms
77,704 KB
testcase_18 AC 130 ms
77,824 KB
testcase_19 AC 137 ms
78,024 KB
testcase_20 AC 128 ms
77,536 KB
testcase_21 AC 1,386 ms
151,196 KB
testcase_22 AC 1,440 ms
150,948 KB
testcase_23 AC 1,417 ms
151,524 KB
testcase_24 AC 1,408 ms
151,024 KB
testcase_25 AC 1,409 ms
150,772 KB
testcase_26 AC 887 ms
151,436 KB
testcase_27 AC 883 ms
150,592 KB
testcase_28 AC 889 ms
151,272 KB
testcase_29 AC 892 ms
150,572 KB
testcase_30 AC 897 ms
150,880 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/1099

class LazySegmentTree:
    """
    非再帰版遅延セグメント木。
    更新は「加法」、取得は「加法」のもの限定。
    取得のところの都合で取得演算子は可換になっている必要がある。
    """

    def __init__(self, init_array):
        n = 1
        while n < len(init_array):
            n *= 2
        
        self.size = n
        self.array = [[0, 0, 0] for _ in range(2 * self.size)]
        self.lazy_array = [0 for _ in range(2 * self.size)]
        for i, a in enumerate(init_array):
            self.array[self.size + i][0] = a ** 2
            self.array[self.size + i][1] = a
            self.array[self.size + i][2] = 1
        
        end_index = self.size
        start_index = end_index // 2
        while start_index >= 1:
            for i in range(start_index, end_index):
                for j in range(3):
                    self.array[i][j] = self.array[2 * i][j] + self.array[2 * i + 1][j]
            end_index = start_index
            start_index = end_index // 2
        
    def _propagates(self, *ids):
        for i in reversed(ids):
            self._propagate(i)

    def _propagate(self, i):
        v = self.lazy_array[i]
        if v == 0:
            return
        
        if i < self.size:
            self.lazy_array[2 * i] += v
            self.lazy_array[2 * i + 1] += v
            self._op(2 * i, v)
            self._op(2 * i + 1, v)
        self.lazy_array[i] = 0

    def _get_target_index(self, l, r):
        L = l + self.size; R = r + self.size
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while 0 < L and L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1
        while L > 0:
            yield L
            L >>= 1

    def _op(self, index, x):
        a1 = self.array[index][1] + self.array[index][2] * x
        a2 = self.array[index][0] + 2 * self.array[index][1] * x + self.array[index][2] * x ** 2
        self.array[index][0] = a2
        self.array[index][1] = a1

    def add(self, l, r, x):
        # 2. 区間[l, r)のdata, lazyの値を更新
        L = self.size + l; R = self.size + r
        *ids, = self._get_target_index(l, r)
        self._propagates(*ids)
        while L < R:
            if R & 1:
                R -= 1
                self.lazy_array[R] += x
                self._op(R, x)
            if L & 1:
                self.lazy_array[L] += x
                self._op(L, x)
                L += 1
            L >>= 1; R >>= 1

        # 3. 伝搬させた区間について、ボトムアップにdataの値を伝搬する
        for i in ids:
            if i < self.size:
                for j in range(3):
                    self.array[i][j] = self.array[2 * i][j] + self.array[2 * i + 1][j]

    def get_square_sum(self, l, r):
        # 1. トップダウンにlazyの値を伝搬
        self._propagates(*self._get_target_index(l, r))
        L = self.size + l; R = self.size + r

        # 2. 区間[l, r)の最大値を求める
        s = 0
        while L < R:
            if R & 1:
                R -= 1
                s += self.array[R][0]
            if L & 1:
                s += self.array[L][0]
                L += 1
            L >>= 1; R >>= 1
        return s


def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    queries = []
    for _ in range(Q):
        values = tuple(map(int, input().split()))
        queries.append(values)

    lazy_seg_tree = LazySegmentTree(A)
    for values in queries:
        if values[0] == 1:
            l = values[1] - 1
            r = values[2] - 1
            x = values[3]
            lazy_seg_tree.add(l, r + 1, x)
        elif values[0] == 2:
            l = values[1] - 1
            r = values[2] - 1
            answer = lazy_seg_tree.get_square_sum(l, r + 1)
            print(answer)











    



if __name__ == "__main__":
    main()
0