点加矩形求和（Point Add Rectangle Sum）

问题描述

给定 $N$ 个带权点在二维平面上。第 $i$ 个点位于 $(x_i, y_i)$，权重为 $w_i$。
处理 $Q$ 个查询，类型如下：

• 0 x y w：在 $(x, y)$ 添加一个权重为 $w$ 的新点；若已有另一点在同一坐标，仍作为独立点添加。
• 1 l d r u：求满足 $l \le x < r$、$d \le y < u$ 的所有点的权重之和。

约束条件

• $1 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $0 \leq x_i, y_i, w_i \leq 10^9$
• 对于类型 0 查询：
  • $0 \leq x, y \leq 10^9$
  • $0 \leq w \leq 10^9$
• 对于类型 1 查询：
  • $0 \leq l < r \leq 10^9$
  • $0 \leq d < u \leq 10^9$

输入

$N\ Q$
$x_0\ y_0\ w_0$
$x_1\ y_1\ w_1$
:
$x_{N-1}\ y_{N-1}\ w_{N-1}$
Query₀
Query₁
:
Query$_{Q-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

11
1111
111000