結果
| 問題 | No.3507 RangeSum RangeUpdate RangeSqrt |
| コンテスト | |
| ユーザー |
 Kurao
|
| 提出日時 | 2026-04-19 10:41:06 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 11,481 bytes |
| 記録 | |
| コンパイル時間 | 525 ms |
| コンパイル使用メモリ | 85,376 KB |
| 実行使用メモリ | 225,756 KB |
| 最終ジャッジ日時 | 2026-04-19 10:56:09 |
| 合計ジャッジ時間 | 8,661 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 1 |
| other | TLE * 1 -- * 28 |
ソースコード
#--------------------------------------------------
import sys
import functools
#sys.setrecursionlimit(10**9)
#codon↓--------------------------------------------
_factorial=[1]
def factorial(n):
while len(_factorial)<=n:
_factorial.append((_factorial[-1]*len(_factorial))%mod)
return _factorial[n]
def binom(n,r):
if r>=mod:
raise ValueError("r is too big")
if n<0:
return 0
if r>n:
return 0
if r<0:
return 0
ans=((factorial(n)*pow(factorial(r),mod-2,mod))%mod*pow(factorial(n-r),mod-2,mod))%mod
return ans
import string
import itertools
alp_low=list(string.ascii_lowercase)
alp_up=list(string.ascii_uppercase)
dij=[[0,1],[1,0],[0,-1],[-1,0]]
mod=998244353
INF=10**18
def dijkstra(edges, num_node,start):
"""
[node_num,weight>0][
(example)
Edges = [
[[1, 4], [2, 3]],
[[0, 1], [3, 1]],
[[3, 2]],
[],
]
"""
import heapq;n=[INF]*num_node;n[start]=0;n_name=[];heapq.heappush(n_name,[0,start])
while len(n_name):
_,min_p=heapq.heappop(n_name)
for f in edges[min_p]:
g,c=f
if n[min_p]+c<n[g]:n[g]=n[min_p]+c;heapq.heappush(n_name,[n[min_p]+c,g])
return n
def nin():
return list(map(int,input().split()))
def deq(x):
return [i-1 for i in x]
def pop_cnt(n):
ans=0
while n:
if n%2:
ans+=1
n//=2
return ans
#↓ Atcoder lib
def _ceil_pow2(n: int) -> int:
x = 0
while (1 << x) < n:
x += 1
return x
def _bsf(n: int) -> int:
x = 0
while n % 2 == 0:
x += 1
n //= 2
return x
import typing
class LazySegTree:
def __init__(
self,
op: typing.Callable[[typing.Any, typing.Any], typing.Any],
e: typing.Any,
mapping: typing.Callable[[typing.Any, typing.Any], typing.Any],
composition: typing.Callable[[typing.Any, typing.Any], typing.Any],
id_: typing.Any,
v: typing.Union[int, typing.List[typing.Any]]) -> None:
self._op = op
self._e = e
self._mapping = mapping
self._composition = composition
self._id = id_
if isinstance(v, int):
v = [e] * v
self._n = len(v)
self._log = _ceil_pow2(self._n)
self._size = 1 << self._log
self._d = [e] * (2 * self._size)
self._lz = [self._id] * self._size
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 set(self, p: int, x: typing.Any) -> None:
assert 0 <= 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: int) -> typing.Any:
assert 0 <= 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: int, right: int) -> typing.Any:
assert 0 <= left <= 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 - 1) >> i)
sml = self._e
smr = 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) -> typing.Any:
return self._d[1]
def apply(self, left: int, right: typing.Optional[int] = None,
f: typing.Optional[typing.Any] = None) -> None:
assert f is not None
if right is None:
p = left
assert 0 <= left < 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)
else:
assert 0 <= left <= 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 = left
r2 = 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 = l2
right = 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: int, g: typing.Callable[[typing.Any], bool]) -> int:
assert 0 <= 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
first = True
while first or (left & -left) != left:
first = False
while left % 2 == 0:
left >>= 1
if not g(self._op(sm, self._d[left])):
while left < self._size:
self._push(left)
left *= 2
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
return self._n
def min_left(self, right: int, g: typing.Any) -> int:
assert 0 <= 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
first = True
while first or (right & -right) != right:
first = False
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)
return 0
def _update(self, k: int) -> None:
self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])
def _all_apply(self, k: int, f: typing.Any) -> None:
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: int) -> None:
self._all_apply(2 * k, self._lz[k])
self._all_apply(2 * k + 1, self._lz[k])
self._lz[k] = self._id
def main():
def isqrt(x):
n=max(0,int(x**0.5)-1)
while (n+1)**2<=x:
n+=1
return n
def sp(x):
now=[]
for _ in range(7):
now.append(x%(1<<64))
x//=1<<64
return now[::-1]
def solve(n,q,a,qs):
#[cnt,non0_cnt,f^0(x),f^1(x),...,f^4(x)]
ans=[]
def op(x,y):
return x+y
def conv(x):
if x==0:
return 1<<64
else:
ans=x
for _ in range(4):
temp=ans%(1<<64)
ans<<=64
ans+=isqrt(temp)
ans<<=64
ans+=1
ans<<=64
ans+=1
return ans
def rot(x):
#print(sp(x),"?")
tail=x%(1<<128)
#print(sp(x))
x>>=128
#print(sp(x))
x<<=64
#print(sp(x))
x+=tail>>64
#print(sp(x))
x<<=128
#print(sp(x))
x|=tail
#print(sp(x))
x&=(1<<(64*7))-1
#print(sp(x),"!")
return x
def mapping(f,x):
if f==-10**9:
return x
elif f<0:
now=x
for _ in range(-f):
now=rot(now)
return now
else:
return (x%(1<<64))*conv(f)
def composition(f,g):
if f==-10**9:
return g
if g==-10**9:
return f
if f>=0:
return f
if g>=0:
return isqrt(g)
else:
return f+g
seg=LazySegTree(op,0,mapping,composition,-10**9,[conv(i) for i in a])
for _ in range(q):
qq=qs[_]
if qq[0]==0:
l,r=qq[1:]
ans.append(seg.prod(l,r)>>(64*6))
elif qq[0]==1:
l,r,x=qq[1:]
seg.apply(l,r,x)
else:
l,r=qq[1:]
seg.apply(l,r,-1)
#print([sp(seg.get(i)) for i in range(n)])
return ans
def solve_naive(n,q,a,qs):
now=a[:]
ans=[]
for _ in range(q):
qq=qs[_]
if qq[0]==0:
l,r=qq[1:]
ans.append(sum(a[l:r]))
elif qq[0]==1:
l,r,x=qq[1:]
for i in range(l,r):
a[i]=x
else:
l,r=qq[1:]
for i in range(l,r):
a[i]=isqrt(a[i])
return ans
n,q=nin()
a=nin()
qs=[nin() for i in range(q)]
ans=solve(n,q,a,qs)
for i in ans:
print(i)
return
import random
for _ in range(1000):
n,q=random.randint(2,100),random.randint(1,100)
a=[random.randint(0,10000000) for _ in range(n) ]
qs=[]
for _ in range(q):
now=random.randint(1,3)
l=random.randint(0,n-2)
r=random.randint(l+1,n-1)
if now==1:
qs.append([now,l,r,random.randint(0,100)])
elif now==2:
qs.append([now,l,r])
else:
qs.append([now,l,r])
ans1=solve(n,q,a,qs)
ans2=solve_naive(n,q,a,qs)
if ans1!=ans2:
print(n,q)
print(*a)
for i in qs:
print(*i)
for i in ans1:
print(i)
for i in ans2:
print(i)
if __name__=="__main__":
main()