3436 . [模板題] Range Affine Range Sum
TopCoder
Tags
Description
Given a size $N$ interger sequence $a_ 0, a_ 1, \dots, a_ {N - 1}$. Process $Q$ queries as follows:
0 l r b c: For each $i = l, l+1, \dots, {r - 1}$, $a_ i \gets b \times a_ i + c$.1 l r: Print $\sum_ {i = l}^ {r - 1} a_ i \bmod 998244353$.
Input Format
$N$ $Q$
$a_ 0$ $a_ 1$ ... $a_ {N - 1}$
$\textrm{Query}_ 0$
$\textrm{Query}_ 1$
:
$\textrm{Query}_ {Q - 1}$
Output Format
Sample Input 1
5 7 1 2 3 4 5 1 0 5 0 2 4 100 101 1 0 3 0 1 3 102 103 1 2 5 0 2 5 104 105 1 0 5
Sample Output 1
15 404 41511 4317767
Hints
- $1 \leq N, Q \leq 5 \times 10^ {5}$
- $0 \leq a_ i, c < 998244353$
- $1 \leq b < 998244353$
- $0 \leq l < r \leq N$
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|