动态序列区间仿射变换区间求和（Dynamic Sequence Range Affine Range Sum）

问题描述

给定一个长度为 $N$ 的整数序列 $a_0, a_1, \dots, a_{N-1}$。
处理 $Q$ 个查询，类型如下：

• 0 i x：在位置 $i$ 插入元素 $x$。若 $i < |a|$，则插入到 $a_i$ 前；若 $i = |a|$，则追加到末尾。
• 1 i：删除第 $i$ 个元素 $a_i$（删除后后续元素前移）。
• 2 l r：将子序列 $a_l, a_{l+1}, \dots, a_{r-1}$ 翻转。
• 3 l r b c：对每个 $i = l, l+1, \dots, r-1$，执行赋值 $a_i \leftarrow b \times a_i + c$。
• 4 l r：输出区间和 $\sum_{i=l}^{r-1} a_i \bmod 998244353$。

约束条件

• $1 \leq N \leq 5 \times 10^5$
• $1 \leq Q \leq 5 \times 10^5$
• $0 \leq a_i < 998244353$
• 对于格式 0 i x：
  • $0 \leq i \leq |a|$（当时序列长度）
  • $0 \leq x < 998244353$
• 对于格式 1 i：
  • $0 \leq i < |a|$
• 对于格式 2 l r：
  • $0 \leq l < r \leq |a|$
• 对于格式 3 l r b c：
  • $0 \leq l < r \leq |a|$
  • $0 \leq b, c < 998244353$
• 对于格式 4 l r：
  • $0 \leq l < r \leq |a|$

输入

$N\ Q$
$a_0\ a_1\ \cdots\ a_{N-1}$
Query₀
Query₁
:
Query$_{Q-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