結果
問題 | No.8110 WIP Editorial |
ユーザー |
|
提出日時 | 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 |
ソースコード
class LazySegTree:def __init__(self, init_value, op, e, mapping, composition, identity):n = len(init_value)self.op = opself.e = eself.mapping = mappingself.composition = compositionself.identity = identityself.size = 1 << (n - 1).bit_length()self.data = [e] * (2 * self.size)self.lazy = [identity] * self.sizefor 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 lif r <= rm: yield rr >>= 1l >>= 1while l:yield ll >>= 1def propagate(self, *ids):for i in reversed(ids):k = i * 2self.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 += 1self.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.identitydef apply(self, l, r, f):if l == r: returnl += self.sizer += 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 += 1if r & 1:r -= 1self.data[r] = self.mapping(f, self.data[r])if r < self.size: self.lazy[r] = self.composition(f, self.lazy[r])l >>= 1r >>= 1for 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.el += self.sizer += self.sizeself.propagate(*self.get_indices(l, r))sl = self.esr = self.ewhile l < r:if l & 1:sl = self.op(sl, self.data[l])l += 1if r & 1:r -= 1sr = self.op(self.data[r], sr)l >>= 1r >>= 1return self.op(sl, sr)MOD = 998244353e = 0identity = 0def op(x, y): return (x // MOD + y // MOD) * MOD + (x + y) % MODdef mapping(f, x):count = x // MODreturn count * MOD + ((f + MOD) * count if f < 0 else f * count + x) % MODdef composition(f, g):if f < 0: return freturn (f + g + MOD) % MOD - MOD if g < 0 else (f + g) % MODN = int(input())A = list(map(int, input().split(' ')))primes = []for x in range(2, 100):ok = Truefor p in primes: ok &= x % p > 0if 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], 0while x % p == 0:x //= pv += 1data[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 -= 1if T == 1:for i in range(C):p, v = primes[i], 0while X % p == 0:X //= pv += 1seg[i].apply(L, R, v - MOD)elif T == 2:for i in range(C):p, v = primes[i], 0while X % p == 0:X //= pv += 1seg[i].apply(L, R, v)else:ans = 1for i in range(C):p = primes[i]if p > X: breakans = ans * (seg[i].prod(L, R) % MOD + 1) % MODprint(ans)