8829: [yosupo] Data Structure - Point Set Range Sort Range Composite
[Creator : ]
Description
A Sequence of triples of integers $\bigl((p_i, a_i, b_i)\bigr)_{0\leq i < N}$ is given.
Process $Q$ queries as follows:
- 0 $i$ $p$ $a$ $b$: change $(p_i,a_i,b_i) \gets (p,a,b)$.
- 1 $l$ $r$ $x$: print $f_{r-1}(f_{r-2}(...f_l(x))) \bmod998244353$, where $f_i(x) := a_ix + b_i$.
- 2 $l$ $r$: Sort $\bigl((p_i, a_i, b_i)\bigr)_{l\leq i < r}$ so that $p_i$ is increasing.
- 3 $l$ $r$: Sort $\bigl((p_i, a_i, b_i)\bigr)_{l\leq i < r}$ so that $p_i$ is decreasing.
Process $Q$ queries as follows:
- 0 $i$ $p$ $a$ $b$: change $(p_i,a_i,b_i) \gets (p,a,b)$.
- 1 $l$ $r$ $x$: print $f_{r-1}(f_{r-2}(...f_l(x))) \bmod998244353$, where $f_i(x) := a_ix + b_i$.
- 2 $l$ $r$: Sort $\bigl((p_i, a_i, b_i)\bigr)_{l\leq i < r}$ so that $p_i$ is increasing.
- 3 $l$ $r$: Sort $\bigl((p_i, a_i, b_i)\bigr)_{l\leq i < r}$ so that $p_i$ is decreasing.
Input
$N$ $Q$
$p_0$ $a_0$ $b_0$
$\vdots$
$p_{N-1}$ $a_{N-1}$ $b_{N-1}$
$\textrm{Query}_0$
$\vdots$
$\textrm{Query}_{Q - 1}$
$p_0$ $a_0$ $b_0$
$\vdots$
$p_{N-1}$ $a_{N-1}$ $b_{N-1}$
$\textrm{Query}_0$
$\vdots$
$\textrm{Query}_{Q - 1}$
Constraints
$1 \leq N \leq 100,000$
$1 \leq Q \leq100,000$
$0 \leq i < N$
$0 \leq p_i, p \leq 10^9$
All values $p_i, p$ (initial values and values given in query 0) are distinct.
$1 \leq a_i, a < 998244353$
$0 \leq b_i, b < 998244353$
$0 \leq x < 998244353$
$0 \leq l < r \leq N$
$1 \leq Q \leq100,000$
$0 \leq i < N$
$0 \leq p_i, p \leq 10^9$
All values $p_i, p$ (initial values and values given in query 0) are distinct.
$1 \leq a_i, a < 998244353$
$0 \leq b_i, b < 998244353$
$0 \leq x < 998244353$
$0 \leq l < r \leq N$
Sample 1 Input
3 8
1 10 1
0 10 2
2 10 3
1 0 3 0
2 0 3
1 0 3 0
3 0 3
1 0 3 0
2 0 2
1 0 3 0
1 1 3 0
Sample 1 Output
123
213
312
132
32
Sample 2 Input
3 10
5 10 1
2 10 2
4 10 3
1 0 3 0
0 1 8 10 4
2 0 3
1 0 3 0
0 1 3 10 5
3 0 3
1 0 3 0
0 0 1 10 6
2 1 3
1 0 3 0
Sample 2 Output
123
314
435
653