8849: [yosupo] Data Structure - Point Add Rectangle Sum
[Creator : ]
Description
You are given $N$ weighted points on two-dimensional plane. $i$-th is at ($x_i$, $y_i$) and has a weight of $w_i$.
Process $Q$ queries of the following types.
- `0 $x$ $y$ $w$` : Add a new point with weight $w$ at $(x, y)$. If there is another point at the same coordinates, add as a distinct point.
- `1 $l$ $d$ $r$ $u$` : Find the sum of weight of points such that $l \leq x < r$, $d \leq y < u$ is satisfied.
Process $Q$ queries of the following types.
- `0 $x$ $y$ $w$` : Add a new point with weight $w$ at $(x, y)$. If there is another point at the same coordinates, add as a distinct point.
- `1 $l$ $d$ $r$ $u$` : Find the sum of weight of points such that $l \leq x < r$, $d \leq y < u$ is satisfied.
Input
$N$ $Q$
$x_0$ $y_0$ $w_0$
$x_1$ $y_1$ $w_1$
$x_2$ $y_2$ $w_2$
$\hspace{17pt} \vdots$
$x_{N - 1}$ $y_{N - 1}$ $w_{N - 1}$
$\mathrm{Query}_0$
$\mathrm{Query}_1$
$\mathrm{Query}_2$
$\hspace{13pt} \vdots$
$\mathrm{Query}_{Q - 1}$
$x_0$ $y_0$ $w_0$
$x_1$ $y_1$ $w_1$
$x_2$ $y_2$ $w_2$
$\hspace{17pt} \vdots$
$x_{N - 1}$ $y_{N - 1}$ $w_{N - 1}$
$\mathrm{Query}_0$
$\mathrm{Query}_1$
$\mathrm{Query}_2$
$\hspace{13pt} \vdots$
$\mathrm{Query}_{Q - 1}$
Constraints
- $1 \le N \le 100,000$
- $1 \le Q \le 100,000$
- $0 \le x_i, y_i \le 10^9$
- $0 \le w_i \le 10^9$
- For queries of type `0 $x$ $y$ $w$`
- $0 \le x, y \le 10^9$
- $0 \le w \le 10^9$
- For queries of type `1 $l$ $d$ $r$ $u$`
- $0 \le l \lt r \le 10^9$
- $0 \le d \lt u \le 10^9$
- $1 \le Q \le 100,000$
- $0 \le x_i, y_i \le 10^9$
- $0 \le w_i \le 10^9$
- For queries of type `0 $x$ $y$ $w$`
- $0 \le x, y \le 10^9$
- $0 \le w \le 10^9$
- For queries of type `1 $l$ $d$ $r$ $u$`
- $0 \le l \lt r \le 10^9$
- $0 \le d \lt u \le 10^9$
Sample 1 Input
4 5
0 0 1
0 2 10
2 0 100
2 2 1000
1 0 0 2 3
1 0 0 3 3
0 2 2 10000
0 1 1 100000
1 1 1 3 3
Sample 1 Output
11
1111
111000