单点加矩形求和

【题目描述】

给定二维平面上的 $N$ 个带权点。第 $i$ 个点位于 ($x_i$, $y_i$)，权值为 $w_i$。 处理 $Q$ 个以下两种类型的查询。

• 0 $x$ $y$ $w$：在 $(x, y)$ 处添加一个权值为 $w$ 的新点。若同一坐标上已有另一个点，则作为不同的点添加。
• 1 $l$ $d$ $r$ $u$：求满足 $l \leq x < r$，$d \leq y < u$ 的点的权值之和。

【输入】

$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}$

【输出】

对每个 1 $l$ $d$ $r$ $u$ 查询，输出一行一个整数，表示所求的权值之和。

【输入样例】

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

【输出样例】

11
1111
111000

【数据范围】

• $1 \le N \le 100000$
• $1 \le Q \le 100000$
• $0 \le x_i, y_i \le 1000000000$
• $0 \le w_i \le 1000000000$
• 对于 0 $x$ $y$ $w$ 类型的查询
  • $0 \le x, y \le 1000000000$
  • $0 \le w \le 1000000000$
• 对于 1 $l$ $d$ $r$ $u$ 类型的查询
  • $0 \le l \lt r \le 1000000000$
  • $0 \le d \lt u \le 1000000000$

【来源】

Library Checker（yosupo06） point_add_rectangle_sum