結果

問題 No.1099 Range Square Sum
コンテスト
ユーザー brthyyjp
提出日時 2022-01-02 15:35:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 872 ms / 2,000 ms
コード長 3,509 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 543 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 134,016 KB
最終ジャッジ日時 2024-10-11 18:50:45
合計ジャッジ時間 12,679 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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