結果

問題 No.3110 WIP Editorial
ユーザー KumaTachiRenKumaTachiRen
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
60,284 KB
testcase_01 AC 1,953 ms
88,292 KB
testcase_02 AC 2,264 ms
94,644 KB
testcase_03 AC 2,383 ms
96,120 KB
testcase_04 AC 2,615 ms
109,404 KB
testcase_05 AC 2,490 ms
107,868 KB
testcase_06 AC 2,737 ms
108,144 KB
testcase_07 AC 2,702 ms
108,460 KB
testcase_08 AC 2,709 ms
107,628 KB
権限があれば一括ダウンロードができます

ソースコード

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)
0