8850: [yosupo] Data Structure - Static Rectangle Add Rectangle Sum
[Creator : ]
Description
You are given a $@{param.X_MAX} \times @{param.Y_MAX}$ matrix $A = (A_{xy})$ ($0\leq x < @{param.X_MAX}$, $0\leq y < @{param.Y_MAX}$).
Initially, all entries $A_{xy}$ equal $0$.
First, process following $N$ queries. - `$l$ $d$ $r$ $u$ $w$`: Add $w$ to all entries $A_{xy}$ satistying $l\leq x < r$ and $d\leq y < u$.
Then, process following $Q$ queries.
- `$l$ $d$ $r$ $u$`: Calculate sum of entries $A_{xy}$ satistying $l\leq x < r$ and $d\leq y < u$, and print it modulo $998244353$.
Initially, all entries $A_{xy}$ equal $0$.
First, process following $N$ queries. - `$l$ $d$ $r$ $u$ $w$`: Add $w$ to all entries $A_{xy}$ satistying $l\leq x < r$ and $d\leq y < u$.
Then, process following $Q$ queries.
- `$l$ $d$ $r$ $u$`: Calculate sum of entries $A_{xy}$ satistying $l\leq x < r$ and $d\leq y < u$, and print it modulo $998244353$.
Input
$N$ $Q$
$l_0$ $d_0$ $r_0$ $u_0$ $w_0$
$\vdots$
$l_{N-1}$ $d_{N-1}$ $r_{N-1}$ $u_{N-1}$ $w_{N-1}$
$l_0$ $d_0$ $r_0$ $u_0$
$\vdots$
$l_{Q-1}$ $d_{Q-1}$ $r_{Q-1}$ $u_{Q-1}$
$l_0$ $d_0$ $r_0$ $u_0$ $w_0$
$\vdots$
$l_{N-1}$ $d_{N-1}$ $r_{N-1}$ $u_{N-1}$ $w_{N-1}$
$l_0$ $d_0$ $r_0$ $u_0$
$\vdots$
$l_{Q-1}$ $d_{Q-1}$ $r_{Q-1}$ $u_{Q-1}$
Constraints
- $1 \leq N \leq 200,000$
- $1 \leq Q \leq 200,000$
- $0 \leq l_i < r_i \leq 10^9$
- $0 \leq d_i < u_i \leq 10^9$
- $0 \leq w_i < 998244353$
- $1 \leq Q \leq 200,000$
- $0 \leq l_i < r_i \leq 10^9$
- $0 \leq d_i < u_i \leq 10^9$
- $0 \leq w_i < 998244353$
Sample 1 Input
2 7
0 0 2 4 1
1 1 3 5 2
0 0 1 1
1 1 2 2
2 2 3 3
0 0 3 5
0 0 3 2
0 1 3 3
3 0 4 4
Sample 1 Output
1
3
2
24
8
12
0