結果

問題 No.1891 Static Xor Range Composite Query
ユーザー gew1fw
提出日時 2025-06-12 20:22:11
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,629 bytes
コンパイル時間 495 ms
コンパイル使用メモリ 81,828 KB
実行使用メモリ 76,812 KB
最終ジャッジ日時 2025-06-12 20:23:18
合計ジャッジ時間 10,135 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20 TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
MOD = 998244353

def main():
    sys.setrecursionlimit(1 << 25)
    N, Q = map(int, sys.stdin.readline().split())
    a_list = []
    b_list = []
    for _ in range(N):
        a, b = map(int, sys.stdin.readline().split())
        a_list.append(a % MOD)
        b_list.append(b % MOD)
    queries = []
    for _ in range(Q):
        l, r, p, x = map(int, sys.stdin.readline().split())
        queries.append((l, r, p, x))

    # 线段树节点结构
    class SegmentTreeNode:
        __slots__ = ['start', 'end', 'a', 'b', 'left', 'right']
        def __init__(self, start, end):
            self.start = start
            self.end = end
            self.a = 0
            self.b = 0
            self.left = None
            self.right = None

    def build(start, end):
        node = SegmentTreeNode(start, end)
        if start + 1 == end:
            node.a = a_list[start]
            node.b = b_list[start]
            return node
        mid = (start + end) // 2
        node.left = build(start, mid)
        node.right = build(mid, end)
        # 父节点的函数是 left_func o right_func
        # a = left.a * right.a
        # b = left.a * right.b + left.b
        node.a = (node.left.a * node.right.a) % MOD
        node.b = (node.left.a * node.right.b + node.left.b) % MOD
        return node

    root = build(0, N)

    def query_range(node, l, r):
        if node.end <= l or node.start >= r:
            return (1, 0)
        if l <= node.start and node.end <= r:
            return (node.a, node.b)
        left_a, left_b = query_range(node.left, l, r)
        right_a, right_b = query_range(node.right, l, r)
        # 合并 right_func o left_func
        if (left_a, left_b) == (1, 0) and (right_a, right_b) == (1, 0):
            return (1, 0)
        if (left_a, left_b) == (1, 0):
            return (right_a, right_b)
        if (right_a, right_b) == (1, 0):
            return (left_a, left_b)
        a = (right_a * left_a) % MOD
        b = (right_a * left_b + right_b) % MOD
        return (a, b)

    for l, r, p, x in queries:
        # 确定实际的区间
        a = 0
        b = 0
        current_a, current_b = 1, 0
        for k in range(l, r):
            idx = (k ^ p)
            if idx < 0 or idx >= N:
                continue
            # current_func = f[idx] o current_func
            new_a = (a_list[idx] * current_a) % MOD
            new_b = (a_list[idx] * current_b + b_list[idx]) % MOD
            current_a, current_b = new_a, new_b
        res = (current_a * x + current_b) % MOD
        print(res)
        
    return

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