結果
| 問題 |
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 |
ソースコード
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])