3744 . [模板題] Point Add Rectangle Sum
TopCoder
Tags
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.
Input Format
$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}$
Output Format
Sample Input 1
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 Output 1
11 1111 111000
Hints
- $1 \le N \le 10^ {5}$
- $1 \le Q \le 10^ {5}$
- $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}$
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|