結果

問題 No.1891 Static Xor Range Composite Query
ユーザー gew1fw
提出日時 2025-06-12 15:14:12
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,356 bytes
コンパイル時間 229 ms
コンパイル使用メモリ 82,688 KB
実行使用メモリ 67,200 KB
最終ジャッジ日時 2025-06-12 15:14:25
合計ジャッジ時間 9,090 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20 TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0

    N = int(input[ptr])
    ptr += 1
    Q = int(input[ptr])
    ptr += 1

    a = []
    b = []
    for _ in range(N):
        ai = int(input[ptr])
        ptr += 1
        bi = int(input[ptr])
        ptr += 1
        a.append(ai % MOD)
        b.append(bi % MOD)

    class SegmentTree:
        def __init__(self, a, b):
            self.n = len(a)
            self.size = 1
            while self.size < self.n:
                self.size <<= 1
            self.a = [1] * (2 * self.size)
            self.b = [0] * (2 * self.size)
            for i in range(self.n):
                self.a[self.size + i] = a[i]
                self.b[self.size + i] = b[i]
            for i in range(self.size - 1, 0, -1):
                self.push_up(i)

        def push_up(self, i):
            left = 2 * i
            right = 2 * i + 1
            self.a[i] = (self.a[left] * self.a[right]) % MOD
            self.b[i] = (self.a[right] * self.b[left] + self.b[right]) % MOD

        def query(self, l, r):
            res_a = 1
            res_b = 0
            l += self.size
            r += self.size
            while l < r:
                if l % 2 == 1:
                    res_a = (res_a * self.a[l]) % MOD
                    res_b = (res_a * self.b[l] + res_b) % MOD
                    l += 1
                if r % 2 == 1:
                    r -= 1
                    res_a = (res_a * self.a[r]) % MOD
                    res_b = (self.a[r] * res_b + res_a * self.b[r]) % MOD
                l >>= 1
                r >>= 1
            return (res_a, res_b)

    st = SegmentTree(a, b)

    for _ in range(Q):
        l = int(input[ptr])
        ptr += 1
        r = int(input[ptr])
        ptr += 1
        p = int(input[ptr])
        ptr += 1
        x = int(input[ptr])
        ptr += 1

        left = l
        right = r - 1
        if left > right:
            print(x % MOD)
            continue

        res_a = 1
        res_b = 0
        i = left
        while i <= right:
            idx = (i ^ p)
            ai = a[idx]
            bi = b[idx]
            res_a = (res_a * ai) % MOD
            res_b = (ai * res_b + bi) % MOD
            i += 1

        res = (res_a * x + res_b) % MOD
        print(res)

if __name__ == "__main__":
    main()
0