結果

問題 No.1099 Range Square Sum
ユーザー Shinya Fujita
提出日時 2025-01-19 12:44:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,611 ms / 2,000 ms
コード長 5,831 bytes
コンパイル時間 497 ms
コンパイル使用メモリ 82,236 KB
実行使用メモリ 170,884 KB
最終ジャッジ日時 2025-01-19 12:44:36
合計ジャッジ時間 17,521 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #

class LazyPropSegTree:
    def __init__(self, op, e, mapping, composition, id_, v=[]):
        assert (len(v) >= 0)
        self.n = len(v)
        self.log = (self.n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [e for _ in range(2*self.size)]
        self.lz = [id_ for _ in range(self.size)]
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.id_ = id_

        for i in range(self.n):
            self.d[self.size + i] = v[i]
        for i in range(self.size - 1, 0, -1):
            self.update(i)

    def update(self, k):
        self.d[k] = self.op(self.d[2*k], self.d[2*k+1])
    
    def all_apply(self, k, f):
        self.d[k] = self.mapping(f, self.d[k])
        if k < self.size:
            self.lz[k] = self.composition(f, self.lz[k])

    def push(self, k):
        self.all_apply(2*k, self.lz[k])
        self.all_apply(2*k+1, self.lz[k])
        self.lz[k] = self.id_

    def set(self, p, x):
        assert (0 <= p) and (p < self.n)
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        self.d[p] = x
        for i in range(1, self.log + 1):
            self.update(p >> i)

    def get(self, p):
        assert (0 <= p) and (p < self.n)
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        return self.d[p]

    def prod(self, left, right):
        assert 0<=left and left<=right and right<=self.n
        if left == right:
            return self.e
        left += self.size
        right += self.size
        for i in range(self.log, 0, -1):
            if (((left >> i) << i) != left):
                self.push(left >> i)
            if (((right >> i) << i) != right):
                self.push(right >> i)
        sml, smr = self.e, self.e
        while left < right:
            if left & 1:
                sml = self.op(sml, self.d[left])
                left += 1
            if right & 1:
                right -= 1
                smr = self.op(self.d[right], smr)
            left >>= 1
            right >>= 1
        return self.op(sml, smr)

    def all_prod(self):
        return self.d[1]

    def apply(self, p, f):
        assert (0 <= p) and (p < self.n)
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        self.d[p] = self.mapping(f, self.d[p])
        for i in range(1, self.log+1):
            self.update(p >> i)

    def apply_lr(self, left, right, f):
        assert 0<=left and left<=right and right<=self.n
        if left == right:
            return
        left += self.size
        right += self.size
        for i in range(self.log, 0, -1):
            if (((left >> i) << i) != left):
                self.push(left >> i)
            if (((right >> i) << i) != right):
                self.push((right - 1) >> i)
        l2, r2 = left, right
        while left < right:
            if left & 1:
                self.all_apply(left, f)
                left += 1
            if right & 1:
                right -= 1
                self.all_apply(right, f)
            left >>= 1
            right >>= 1
        left, right = l2, r2
        for i in range(1,self.log+1):
            if (((left >> i) << i) != left):
                self.update(left >> i)
            if (((right >> i) << i) != right):
                self.update((right-1) >> i)
    
    def max_right(self, left, g):
        assert (0 <= left) and (left <= self.n)
        assert g(self.e)
        if left == self.n:
            return self.n
        left += self.size
        for i in range(self.log, 0, -1):
            self.push(left >> i)
        sm = self.e
        while True:
            while(left % 2 == 0):
                left >>= 1
            if not g(self.op(sm, self.d[left])):
                while left < self.size:
                    self.push(left)
                    left <<= 1
                    if g(self.op(sm, self.d[left])):
                        sm = self.op(sm, self.d[left])
                        left += 1
                return left - self.size
            sm = self.op(sm, self.d[left])
            left += 1
            if(left & -left) == left:
                break
        return self.n

    def min_left(self, right, g):
        assert (0 <= right) and (right <= self.n)
        assert g(self.e)
        if right == 0:
            return 0
        right += self.size
        for i in range(self.log, 0, -1):
            self.push((right-1) >> i)
        sm = self.e
        while True:
            right -= 1
            while(right > 1) and (right % 2):
                right >>= 1
            if not g(self.op(self.d[right], sm)):
                while right < self.size:
                    self.push(right)
                    right = 2 * right + 1
                    if g(self.op(self.d[right], sm)):
                        sm = self.op(self.d[right], sm)
                        right -= 1
                return right + 1 - self.size
            sm = self.op(self.d[right], sm)
            if(right & -right) == right:
                break
        return 0


N = int(input())
A = list(map(int, input().split()))


def op(x, y):
    res = [x[0]+y[0], x[1]+y[1], x[2]+y[2]]
    return res

e = [0, 0, 0]

def mapping(p, x):
    cnt = x[2]
    x[0] += cnt*pow(p,2) + 2*p*x[1]
    x[1] += cnt * p
    return x

composition = lambda p,q: p+q

id_ = 0

seg = LazyPropSegTree(
    op=op, e=e, mapping=mapping, composition=composition, id_=id_,
    v=[[a**2, a, 1] for a in A]
)


Q = int(input())
for _ in range(Q):
    q = list(map(int, input().split()))
    if q[0] == 1:
        li, ri, x = q[1:]
        seg.apply_lr(li-1, ri, x)
    else:
        li, ri = q[1:]
        res = seg.prod(li-1, ri)
        print(res[0])
0