結果

問題 No.1099 Range Square Sum
ユーザー brthyyjpbrthyyjp
提出日時 2022-01-02 15:35:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 804 ms / 2,000 ms
コード長 3,509 bytes
コンパイル時間 503 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 134,016 KB
最終ジャッジ日時 2024-04-19 23:57:29
合計ジャッジ時間 11,153 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
52,736 KB
testcase_01 AC 38 ms
52,864 KB
testcase_02 AC 40 ms
52,736 KB
testcase_03 AC 39 ms
52,864 KB
testcase_04 AC 37 ms
52,992 KB
testcase_05 AC 39 ms
52,480 KB
testcase_06 AC 39 ms
53,120 KB
testcase_07 AC 37 ms
52,864 KB
testcase_08 AC 39 ms
52,736 KB
testcase_09 AC 40 ms
52,864 KB
testcase_10 AC 38 ms
52,608 KB
testcase_11 AC 111 ms
77,380 KB
testcase_12 AC 115 ms
76,496 KB
testcase_13 AC 110 ms
76,260 KB
testcase_14 AC 108 ms
76,440 KB
testcase_15 AC 115 ms
76,780 KB
testcase_16 AC 111 ms
76,852 KB
testcase_17 AC 110 ms
77,536 KB
testcase_18 AC 106 ms
77,440 KB
testcase_19 AC 104 ms
76,244 KB
testcase_20 AC 108 ms
76,544 KB
testcase_21 AC 804 ms
133,632 KB
testcase_22 AC 773 ms
134,016 KB
testcase_23 AC 766 ms
133,632 KB
testcase_24 AC 737 ms
133,504 KB
testcase_25 AC 782 ms
133,632 KB
testcase_26 AC 528 ms
132,736 KB
testcase_27 AC 563 ms
132,608 KB
testcase_28 AC 572 ms
133,100 KB
testcase_29 AC 565 ms
132,864 KB
testcase_30 AC 546 ms
132,992 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class LazySegTree:
    def __init__(self, init_val, seg_ide, lazy_ide, f, g, h):
        self.n = len(init_val)
        self.num = 2**(self.n-1).bit_length()

        self.seg_ide = seg_ide
        self.lazy_ide = lazy_ide

        self.f = f
        self.g = g
        self.h = h

        self.seg = [seg_ide]*2*self.num
        for i in range(self.n):
            self.seg[i+self.num] = init_val[i]
        for i in range(self.num-1, 0, -1):
            self.seg[i] = self.f(self.seg[2*i], self.seg[2*i+1])

        self.size = [0]*2*self.num
        for i in range(self.n):
            self.size[i+self.num] = 1
        for i in range(self.num-1, 0, -1):
            self.size[i] = self.size[2*i] + self.size[2*i+1]

        self.lazy = [lazy_ide]*2*self.num

    def update(self, i, x):
        i += self.num
        self.seg[i] = x
        while i:
            i = i >> 1
            self.seg[i] = self.f(self.seg[2*i], self.seg[2*i+1])

    def calc(self, i):
        return self.g(self.seg[i], self.lazy[i], self.size[i])

    def calc_above(self, i):
        i = i >> 1
        while i:
            self.seg[i] = self.f(self.calc(2*i), self.calc(2*i+1))
            i = i >> 1

    def propagate(self, i):
        self.seg[i] = self.g(self.seg[i], self.lazy[i], self.size[i])
        self.lazy[2*i] = self.h(self.lazy[2*i], self.lazy[i])
        self.lazy[2*i+1] = self.h(self.lazy[2*i+1], self.lazy[i])
        self.lazy[i] = self.lazy_ide

    def propagate_above(self, i):
        H = i.bit_length()
        for h in range(H, 0, -1):
            self.propagate(i >> h)

    def query(self, l, r):
        l += self.num
        r += self.num
        lm = l // (l & -l)
        rm = r // (r & -r) -1
        self.propagate_above(lm)
        self.propagate_above(rm)

        al = self.seg_ide
        ar = self.seg_ide
        while l < r:
            if l & 1:
                al = self.f(al, self.calc(l))
                l += 1
            if r & 1:
                r -= 1
                ar = self.f(self.calc(r), ar)
            l = l >> 1
            r = r >> 1
        return self.f(al, ar)

    def operate_range(self, l, r, a):
        l += self.num
        r += self.num
        lm = l // (l & -l)
        rm = r // (r & -r) -1
        self.propagate_above(lm)
        self.propagate_above(rm)
        while l < r:
            if l & 1:
                self.lazy[l] = self.h(self.lazy[l], a)
                l += 1
            if r & 1:
                r -= 1
                self.lazy[r] = self.h(self.lazy[r], a)
            l = l >> 1
            r = r >> 1

        self.calc_above(lm)
        self.calc_above(rm)

    def __str__(self): # for debug
        arr = [self.query(i,i+1) for i in range(self.n)]
        return str(arr)

def f(x, y):
    return (x[0]+y[0], x[1]+y[1])

def g(x, a, s):
    return x[0]+a*s, x[1]+2*x[0]*a+s*a**2

h = lambda a, b: a+b

import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

def main():

    n = int(input())
    A = list(map(int, input().split()))
    q = int(input())
    B = []
    for a in A:
        B.append((a, a**2))
    seg = LazySegTree(B, (0, 0), 0, f, g, h)
    for i in range(q):
        temp = list(map(int, input().split()))
        if temp[0] == 1:
            l, r, x = temp[1:]
            l, r = l-1, r-1
            seg.operate_range(l, r+1, x)
        else:
            l, r = temp[1:]
            l, r = l-1, r-1
            print(seg.query(l, r+1)[1])

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