矩形加点查询（Rectangle Add Point Get）

问题描述

给定 $N$ 个带权矩形在二维平面上。第 $i$ 个矩形的位置为

$$[l_i, r_i) \times [d_i, u_i) = \{ (x, y) \in \mathbb{R}^2 \mid l_i \le x < r_i,\ d_i \le y < u_i \}$$

权重为 $w_i$。

处理 $Q$ 个查询，类型如下：

• 0 l r d u w：添加一个新矩形，位置为 $[l, r) \times [d, u)$，权重为 $w$。
• 1 x y：求所有包含点 $(x, y)$ 的矩形的权重之和（即满足 $l_i \le x < r_i$ 且 $d_i \le y < u_i$ 的矩形 $i$ 的 $w_i$ 之和）。

约束条件

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

输入

$N\ Q$
$l_0\ d_0\ r_0\ u_0\ w_0$
$l_1\ d_1\ r_1\ u_1\ w_1$
:
$l_{N-1}\ d_{N-1}\ r_{N-1}\ u_{N-1}\ w_{N-1}$
Query₀
Query₁
:
Query$_{Q-1}$

4 9
1 2 2 3 1
1 1 2 5 10
2 2 5 5 100
3 1 5 2 1000
1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
1 3 2
1 3 3

10
11
10
0
100
100
1000
100
100

2 8
1 2 2 3 1
1 1 2 5 10
1 1 2
1 2 3
0 1 1 3 3 100
1 1 2
1 2 3
0 2 1 3 5 1000
1 1 2
1 2 3

11
0
111
0
111
1000