11254: [yosupo] Data Structure - Range Reverse Range Sum
[Creator : ]
Description
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 $l$ $r$` : Reverse $a _ l, a _ {l + 1}, \dots, a _ {r - 1}$.
- `1 $l$ $r$` : Print $\sum _ {i = l} ^ {r - 1} a _ i$.
Process $Q$ queries of the following types in order :
- `0 $l$ $r$` : Reverse $a _ l, a _ {l + 1}, \dots, a _ {r - 1}$.
- `1 $l$ $r$` : Print $\sum _ {i = l} ^ {r - 1} a _ i$.
Input
$N$ $Q$
$a _ 0$ $a _ 1$ $\cdots$ $a _ {N - 1}$
$t _ 0$ $l _ 0$ $r _ 0$
$t _ 1$ $l _ 1$ $r _ 1$
$\vdots$
$t _ {Q - 1}$ $l _ {Q - 1}$ $r _ {Q - 1}$
$a _ 0$ $a _ 1$ $\cdots$ $a _ {N - 1}$
$t _ 0$ $l _ 0$ $r _ 0$
$t _ 1$ $l _ 1$ $r _ 1$
$\vdots$
$t _ {Q - 1}$ $l _ {Q - 1}$ $r _ {Q - 1}$
Constraints
- $0 \leq N \leq 2\times 10^5$
- $0 \leq Q \leq 2\times 10^5$
- $0 \leq a _ i \leq 10^9$
- $0 \leq l _ j \leq r _ j \leq N$
- $0 \leq Q \leq 2\times 10^5$
- $0 \leq a _ i \leq 10^9$
- $0 \leq l _ j \leq r _ j \leq N$
Sample 1 Input
4 5
1 2 3 4
1 1 3
0 2 4
1 0 3
0 4 4
1 0 0
Sample 1 Output
5
7
0