1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
# 块状数组
from math import isqrt
def apply(a,l,r,x):
if [l,r]==[a*sq,a*sq+sq-1]:
f[a] += x
return
for i in range(a*sq,min(n,a*sq+sq)):
A[i] += f[a]
if l<=i<=r:
A[i] += x
B[a] = set(A[a*sq:a*sq+sq])
f[a] = 0
def update(l,r,x):
a,b = l//sq,r//sq
if a==b:
apply(a,l,r,x)
else:
apply(a,l,a*sq+sq-1,x)
apply(b,b*sq,r,x)
for i in range(a+1,b):
f[i] += x
A = []
n = len(A)
sq = isqrt(n)
m = (n-1)//sq+1
B = [0]*m
f = [0]*m
for a in range(m):
B[a] = set(A[a*sq:a*sq+sq])
|