8848: [yosupo] Data Structure - Rectangle Sum
[Creator : ]
Description
There are $N$ weighted points on the $2$ dimensional plane. The coordinate of the $i$-th point is $(x_i, y_i)$, and its weight is $w_i$.
Process $Q$ queries.
- $l$ $d$ $r$ $u$: Find the sum of weights of all points that satisfy $l \leq x < r$, $d \leq y < u$.
Process $Q$ queries.
- $l$ $d$ $r$ $u$: Find the sum of weights of all points that satisfy $l \leq x < r$, $d \leq y < u$.
Input
$N$ $Q$
$x_0$ $y_0$ $w_0$
$x_1$ $y_1$ $w_1$
:
$x_{N - 1}$ $y_{N - 1}$ $w_{N - 1}$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q - 1}$
$x_0$ $y_0$ $w_0$
$x_1$ $y_1$ $w_1$
:
$x_{N - 1}$ $y_{N - 1}$ $w_{N - 1}$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q - 1}$
Constraints
$1 \leq N, Q \leq 200,000$
$0 \leq x_i, y_i, w_i \leq 10^9$
$0 \leq l_i < r_i \leq 10^9$
$0 \leq d_i < u_i \leq 10^9$
$0 \leq x_i, y_i, w_i \leq 10^9$
$0 \leq l_i < r_i \leq 10^9$
$0 \leq d_i < u_i \leq 10^9$
Sample 1 Input
5 5
0 0 1
3 0 10
1 4 100
2 2 1000
3 2 10000
0 0 4 5
0 0 4 4
3 0 4 3
2 0 4 3
1 2 2 4
Sample 1 Output
11111
11011
10010
11010
0