結果
問題 | No.1099 Range Square Sum |
ユーザー |
👑 |
提出日時 | 2022-04-17 17:58:53 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 5,105 bytes |
コンパイル時間 | 314 ms |
コンパイル使用メモリ | 81,824 KB |
実行使用メモリ | 281,232 KB |
最終ジャッジ日時 | 2024-12-26 11:22:21 |
合計ジャッジ時間 | 22,096 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 25 TLE * 5 |
ソースコード
"""a <- a + xa^2 <- a^2 + 2ax + x^2"""class lazy_segtree():def __init__(self, lst, ope, e, mapping, composition, id_):self.n = len(lst)self.log = (self.n - 1).bit_length()self.size = 1 << self.logself.data = [e for _ in range(2 * self.size)]self.lz = [id_ for _ in range(self.size)]self.e = eself.op = opeself.mapping = mappingself.composition = compositionself.identity = id_for i in range(self.n):self.data[self.size + i] = lst[i]for i in range(self.size - 1, 0, -1):self.update(i)def update(self, k):self.data[k] = self.op(self.data[2 * k], self.data[2 * k + 1])def all_apply(self, k, f):self.data[k] = self.mapping(f, self.data[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.identitydef set(self, p, x):p += self.sizefor i in range(self.log, 0, -1):self.push(p >> i)self.data[p] = xfor i in range(1, self.log + 1):self.update(p >> i)def get(self, p):p += self.sizefor i in range(self.log, 0, -1):self.push(p >> i)return self.data[p]def prod(self, l, r):if l == r: return self.el += self.sizer += self.sizefor i in range(self.log, 0, -1):if (l >> i) << i != l:self.push(l >> i)if (r >> i) << i != r:self.push(r >> i)sml, smr = self.e, self.ewhile l < r:if l & 1:sml = self.op(sml, self.data[l])l += 1if r & 1:r -= 1smr = self.op(self.data[r], smr)l >>= 1r >>= 1return self.op(sml, smr)def all_prod(self):return self.data[1]def apply_point(self, p, f):p += self.sizefor i in range(self.log, 0, -1):self.push(p >> i)self.data[p] = self.mapping(f, self.data[p])for i in range(1, self.log + 1):self.update(p >> i)def apply(self, l, r, f):if l == r: returnl += self.sizer += self.sizefor i in range(self.log, 0, -1):if (l >> i) << i != l:self.push(l >> i)if (r >> i) << i != r:self.push((r - 1) >> i)l2, r2 = l, rwhile l < r:if l & 1:self.all_apply(l, f)l += 1if r & 1:r -= 1self.all_apply(r, f)l >>= 1r >>= 1l, r = l2, r2for i in range(1, self.log + 1):if (l >> i) << i != l:self.update(l >> i)if (r >> i) << i != r:self.update((r - 1) >> i)def max_right(self, l, g):if l == self.n: return self.nl += self.sizefor i in range(self.log, 0, -1):self.push(l >> i)sm = self.ewhile 1:while i % 2 == 0:l >>= 1if not g(self.op(sm, self.data[l])):while l < self.size:self.push(l)l *= 2if g(self.op(sm, self.data[l])):sm = self.op(sm, self.data[l])l += 1return l - self.sizesm = self.op(sm, self.data[l])l += 1if l & -l == l:breakreturn self.ndef min_left(self, r, g):if r == 0:return 0r += self.sizefor i in range(self.log, 0, -1):self.push((r - 1) >> i)sm = self.ewhile 1:r -= 1while r > 1 and r % 2 == 1:r >>= 1if not g(self.op(self.data[r], sm)):while r < self.size:self.push(r)r = 2 * r + 1if g(self.op(self.data[r], sm)):sm = self.op(self.data[r], sm)r -= 1return r + 1 - self.sizesm = self.op(self.data[r], sm)if r & -r == r:breakreturn 0n = int(input())A = list(map(int, input().split()))def ope(x, y):return (x[0] + y[0], x[1] + y[1], x[2] + y[2])e = (0, 0, 0)def mapping(f, x):return (x[0], x[1] + f * x[0], x[2] + 2 * x[1] * f + x[0] * f * f)def composition(f, g):return f + gseg = lazy_segtree([(1, a, a * a) for a in A], ope, e, mapping, composition, 0)Q = int(input())for _ in range(Q):query = list(map(int, input().split()))if query[0] == 1:l, r, x = query[1:]seg.apply(l - 1, r, x)else:l, r = query[1:]print(seg.prod(l - 1, r)[2])