結果

問題 No.8110 WIP Editorial
ユーザー KumaTachiRen
提出日時 2024-03-06 13:29:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,737 ms / 4,000 ms
コード長 4,001 bytes
コンパイル時間 184 ms
コンパイル使用メモリ 82,288 KB
実行使用メモリ 109,404 KB
最終ジャッジ日時 2024-09-29 21:25:48
合計ジャッジ時間 20,940 ms
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

class LazySegTree:
def __init__(self, init_value, op, e, mapping, composition, identity):
n = len(init_value)
self.op = op
self.e = e
self.mapping = mapping
self.composition = composition
self.identity = identity
self.size = 1 << (n - 1).bit_length()
self.data = [e] * (2 * self.size)
self.lazy = [identity] * self.size
for i in range(n):
self.data[self.size + i] = init_value[i]
for i in range(self.size - 1, 0, -1):
self.data[i] = self.op(self.data[2 * i], self.data[2 * i + 1])
def get_indices(self, l, r):
lm = l >> (l & -l).bit_length()
rm = r >> (r & -r).bit_length()
while r > l:
if l <= lm: yield l
if r <= rm: yield r
r >>= 1
l >>= 1
while l:
yield l
l >>= 1
def propagate(self, *ids):
for i in reversed(ids):
k = i * 2
self.data[k] = self.mapping(self.lazy[i], self.data[k])
if k < self.size: self.lazy[k] = self.composition(self.lazy[i], self.lazy[k])
k += 1
self.data[k] = self.mapping(self.lazy[i], self.data[k])
if k < self.size: self.lazy[k] = self.composition(self.lazy[i], self.lazy[k])
self.lazy[i] = self.identity
def apply(self, l, r, f):
if l == r: return
l += self.size
r += self.size
*ids, = self.get_indices(l, r)
self.propagate(*ids)
while l < r:
if l & 1:
self.data[l] = self.mapping(f, self.data[l])
if l < self.size: self.lazy[l] = self.composition(f, self.lazy[l])
l += 1
if r & 1:
r -= 1
self.data[r] = self.mapping(f, self.data[r])
if r < self.size: self.lazy[r] = self.composition(f, self.lazy[r])
l >>= 1
r >>= 1
for i in ids:
self.data[i] = self.op(self.data[2 * i], self.data[2 * i + 1])
def prod(self, l, r):
if l == r: return self.e
l += self.size
r += self.size
self.propagate(*self.get_indices(l, r))
sl = self.e
sr = self.e
while l < r:
if l & 1:
sl = self.op(sl, self.data[l])
l += 1
if r & 1:
r -= 1
sr = self.op(self.data[r], sr)
l >>= 1
r >>= 1
return self.op(sl, sr)
MOD = 998244353
e = 0
identity = 0
def op(x, y): return (x // MOD + y // MOD) * MOD + (x + y) % MOD
def mapping(f, x):
count = x // MOD
return count * MOD + ((f + MOD) * count if f < 0 else f * count + x) % MOD
def composition(f, g):
if f < 0: return f
return (f + g + MOD) % MOD - MOD if g < 0 else (f + g) % MOD
N = int(input())
A = list(map(int, input().split(' ')))
primes = []
for x in range(2, 100):
ok = True
for p in primes: ok &= x % p > 0
if ok: primes.append(x)
C = len(primes)
data = [[] for _ in range(C)]
for j in range(N):
x = A[j]
for i in range(C):
p, v = primes[i], 0
while x % p == 0:
x //= p
v += 1
data[i].append(MOD + v)
seg = [LazySegTree(data[i], op, e, mapping, composition, identity) for i in range(C)]
Q = int(input())
for _ in range(Q):
T, L, R, X = map(int, input().split(' '))
L -= 1
if T == 1:
for i in range(C):
p, v = primes[i], 0
while X % p == 0:
X //= p
v += 1
seg[i].apply(L, R, v - MOD)
elif T == 2:
for i in range(C):
p, v = primes[i], 0
while X % p == 0:
X //= p
v += 1
seg[i].apply(L, R, v)
else:
ans = 1
for i in range(C):
p = primes[i]
if p > X: break
ans = ans * (seg[i].prod(L, R) % MOD + 1) % MOD
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0