Queue Operate All Composite

AC一覧

Problem Statement
問題文

There is an initially empty sequence of linear functions $f = ()$. Process $Q$ queries.

  • 0 $a$ $b$: Add a linear function $\lambda x. ax + b$ to the end of the sequence $f$.
  • 1: Remove the linear function at the beginning of the sequence $f$.
  • 2 $x$: Let $f = (f_{l}, \dots, f_{r - 1})$, output $f _ {r - 1}(f _ {r - 2}(\dots (f _ l(x)) \dots)) \bmod 998244353$. Output $x$ if $f = ()$.

長さ $0$ (一次)関数の列 $f = ()$ があります。$Q$ 個のクエリが飛んできます。処理してください。

  • 0 $a$ $b$: 列 $f$ の末尾に一次関数 $\lambda x. ax + b$ を追加する
  • 1: 列 $f$ の先頭の一次関数を削除する
  • 2 $x$: $f = (f_{l}, \dots, f_{r - 1})$ として $f _ {r - 1}(f _ {r - 2}(\dots (f _ l(x)) \dots)) \bmod 998244353$ を出力する。$f = ()$ の場合は $x$

Constraints
制約

  • $1 \leq Q \leq 500,000$
  • $1 \leq a \lt 998244353$
  • $0 \leq b, x \lt 998244353$
  • The sequence $f$ is not empty when query $1$ comes.
  • $1 \leq Q \leq 500,000$
  • $1 \leq a \lt 998244353$
  • $0 \leq b, x \lt 998244353$
  • クエリ $1$ が来るとき、列 $f$ は空ではない

Input
入力

$Q$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q - 1}$

# 1

6
0 4 5
2 3
0 2 1
2 2
1
2 3
17
27
7

# 2

1
2 1333
1333

Forum


Timelimit: 5 secs

Before submitting, please confirm terms and conditions