結果
問題 | No.1099 Range Square Sum |
ユーザー |
![]() |
提出日時 | 2020-09-16 01:17:36 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,017 bytes |
コンパイル時間 | 211 ms |
コンパイル使用メモリ | 82,792 KB |
実行使用メモリ | 128,640 KB |
最終ジャッジ日時 | 2024-06-22 02:55:43 |
合計ジャッジ時間 | 13,446 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 1 WA * 29 |
ソースコード
import sys; input = sys.stdin.buffer.readlinesys.setrecursionlimit(10**7)INF = float("inf")def getlist():return list(map(int, input().split()))class lazySegTree(object):def __init__(self, N):self.N = Nself.LV = (N - 1).bit_length()self.N0 = 2 ** self.LVself.ans = [0] * (2 * self.N0)self.data = [0] * (2 * self.N0)self.lazy = [0] * (2 * self.N0)self.lazy2 = [0] * (2 * self.N0)def initialize(self, A):for i in range(self.N):self.data[self.N0 - 1 + i] = A[i]self.ans[self.N0 - 1 + i] = A[i] ** 2for i in range(self.N0 - 2, -1, -1):self.data[i] = self.data[2 * i + 1] + self.data[2 * i + 2]self.ans[i] = self.ans[2 * i + 1] + self.ans[2 * i + 2]def gindex(self, l, r):L = (l + self.N0) >> 1; R = (r + self.N0) >> 1lc = 0 if l & 1 else (L & -L).bit_length()rc = 0 if r & 1 else (R & -R).bit_length()for i in range(self.LV):if rc <= i:yield Rif L < R and lc <= i:yield LL >>= 1; R >>= 1def propagates(self, *ids):for i in reversed(ids):v = self.lazy[i - 1]v2 = self.lazy2[i - 1]if (not v) and (not v2):continueval = v2 >> 1vvv = v >> 1self.ans[2 * i - 1] += 2 * vvv * self.data[2 * i - 1] + valself.ans[2 * i] += 2 * vvv * self.data[2 * i] + valself.data[2 * i - 1] += vvvself.data[2 * i] += vvvself.lazy[2 * i - 1] += vvvself.lazy[2 * i] += vvvself.lazy2[2 * i - 1] += valself.lazy2[2 * i] += valself.lazy[i - 1] = 0; self.lazy2[i - 1] = 0def add(self, l, r, x):*ids, = self.gindex(l, r + 1)self.propagates(*ids)L = self.N0 + l; R = self.N0 + r + 1weight = 1while L < R:if R & 1:R -= 1self.lazy[R - 1] += x * weightself.lazy2[R - 1] += weight * (x ** 2)self.ans[R - 1] += 2 * self.data[R - 1] * weight * x + weight * (x ** 2)self.data[R - 1] += weight * xif L & 1:self.lazy[L - 1] += x * weightself.lazy2[L - 1] += weight * (x ** 2)self.ans[L - 1] += 2 * self.data[L - 1] * weight * x + weight * (x ** 2)self.data[L - 1] += weight * xL += 1L >>= 1; R >>= 1; weight <<= 1for i in ids:self.data[i - 1] = self.data[2 * i - 1] + self.data[2 * i]self.ans[i - 1] = self.ans[2 * i - 1] + self.ans[2 * i]def query(self, l, r):self.propagates(*self.gindex(l, r + 1))L = self.N0 + l; R = self.N0 + r + 1s = 0while L < R:if R & 1:R -= 1s += self.ans[R - 1]if L & 1:s += self.ans[L - 1]L += 1L >>= 1; R >>= 1return sdef debug(self):ids = [i for i in range(self.N0, 0, -1)]self.propagates(*ids)print(self.data[self.N0 - 1:])print(self.ans[self.N0 - 1:])print()def main():N = int(input())A = getlist()lSeg = lazySegTree(N)lSeg.initialize(A)Q = int(input())for i in range(Q):q = getlist()if q[0] == 1:_, l, r, x = ql -= 1; r -= 1lSeg.add(l, r, x)else:_, l, r = ql -= 1; r -= 1ans = lSeg.query(l, r)print(ans)# lSeg.debug()if __name__ == '__main__':main()