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$

長さ $N$ の数列 $a_0, a_1, ..., a_{N-1}$ に $Q$ 個のクエリが飛んできます。処理してください。

  • 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

Forum


Timelimit: 10 secs

Before submitting, please confirm terms and conditions