# Dynamic Sequence Range Affine Range Sum

AC一覧

## Problem Statement問題文

You are given a sequence $a_0, a_1, ..., a_{N - 1}$, consisting of $N$ integers.

Process $Q$ queries of the following types in order :

• 0 $i$ $x$ :
• If $i < |a|$, insert $x$ immediately before $a_i$
• If $i = |a|$, insert $x$ after $a_{|a| - 1}$
• 1 $i$ : Remove $a_i$ (remaining elements will be concatenated)
• 2 $l$ $r$ : Reverse $a_l, a_{l + 1}, a_{l + 2}, \dots, a_{r - 1}$
• 3 $l$ $r$ $b$ $c$ : For each $i = l, l + 1, l + 2, \dots, {r - 1}$, $a_i \gets b \times a_i + c$
• 4 $l$ $r$ : Print $\sum_{i = l}^{r - 1} a_i \bmod 998{,}244{,}353$

• 0 $i$ $x$ :
• $i < |a|$ なら $x$ を $a_i$ の直前に挿入する
• $i = |a|$ なら $x$ を $a_{|a| - 1}$ の後に挿入する
• 1 $i$ : $a_i$ を削除する (残った要素は連結される)
• 2 $l$ $r$ : $a_l, a_{l + 1}, a_{l + 2}, \dots, a_{r - 1}$ を反転する
• 3 $l$ $r$ $b$ $c$ : 各 $i = l, l + 1, l + 2, \dots, {r - 1}$ について $a_i \gets b \times a_i + c$
• 4 $l$ $r$ : $\sum_{i = l}^{r - 1} a_i \bmod 998{,}244{,}353$ を出力する

## Constraints制約

• $1 \le N, Q \le 500{,}000$
• $0 \le a_i \lt 998{,}244{,}353$
• For the format 0 $i$ $x$ :
• $0 \le i \le (|a|$ at the time$)$
• $0 \le x \lt 998{,}244{,}353$
• For the format 1 $i$ :
• $0 \le i \lt (|a|$ at the time$)$
• For the format 2 $l$ $r$ :
• $0 \le l \lt r \le (|a|$ at the time$)$
• For the format 3 $l$ $r$ $b$ $c$ :
• $0 \le l \lt r \le (|a|$ at the time$)$
• $0 \le b \lt 998{,}244{,}353$
• $0 \le c \lt 998{,}244{,}353$
• For the format 4 $l$ $r$ :
• $0 \le l \lt r \le (|a|$ at the time$)$
• $1 \le N, Q \le 500{,}000$
• $0 \le a_i \lt 998{,}244{,}353$
• 0 $i$ $x$ 形式について :
• $0 \le i \le ($その時点での $|a|)$
• $0 \le x \lt 998{,}244{,}353$
• 1 $i$ 形式について :
• $0 \le i \lt ($その時点での $|a|)$
• 2 $l$ $r$ 形式について :
• $0 \le l \lt r \le ($その時点での $|a|)$
• 3 $l$ $r$ $b$ $c$ 形式について :
• $0 \le l \lt r \le ($その時点での $|a|)$
• $0 \le b \lt 998{,}244{,}353$
• $0 \le c \lt 998{,}244{,}353$
• 4 $l$ $r$ 形式について :
• $0 \le l \lt r \le ($その時点での $|a|)$

## Input入力

$N$ $Q$
$a_0$ $a_1$ ... $a_{N - 1}$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q - 1}$


### # 1

5 6
1 10 100 1000 10000
4 1 4
0 2 100000
1 3
4 2 5
2 2 5
4 0 4

1110
111000
11011


Timelimit: 10 secs

Before submitting, please confirm terms and conditions