Day 158-Q1 — SWAG（Sliding Window Aggregation・2スタックで作る「畳み込み可能キュー」）

📋 コピーimport sys

MOD = 998244353
ID = (1, 0)  # 恒等関数 x -> x


def comp(f, g):
    """f を先に適用し、その後 g を適用した合成 g(f(x)) を返す。"""
    return (f[0] * g[0] % MOD, (f[1] * g[0] + g[1]) % MOD)


def main():
    data = sys.stdin.buffer.read().split()
    q = int(data[0])
    pos = 1
    front = []          # 各要素 = 「その要素 ～ front の底（キュー中央側）」までの合成
    back = []           # 生の関数
    back_fold = ID      # back 全体の合成（先に入った順に適用）
    out = []
    for _ in range(q):
        t = data[pos]
        if t == b'0':
            f = (int(data[pos + 1]), int(data[pos + 2]))
            pos += 3
            back.append(f)
            back_fold = comp(back_fold, f)
        elif t == b'1':
            pos += 1
            if not front:
                acc = ID
                while back:                 # 末尾側から取り出す
                    f = back.pop()
                    acc = comp(f, acc)      # f を先に、既に積んだ(より後ろの)関数を後に
                    front.append(acc)
                back_fold = ID
            front.pop()
        else:
            x = int(data[pos + 1])
            pos += 2
            a, b = comp(front[-1] if front else ID, back_fold)
            out.append((a * x + b) % MOD)
    sys.stdout.write("\n".join(map(str, out)) + ("\n" if out else ""))


main()