矩形加点求和

【题目描述】

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

权值为 $w_i$。现在依次处理 $Q$ 个操作，操作分两种：

• 0 l d r u w：在 $[l,r) \times [d,u)$ 处添加一个权值为 $w$ 的新矩形；
• 1 x y：求所有包含点 $(x,y)$ 的矩形的权值之和。

【输入】

第一行包含两个整数 $N$ 和 $Q$，表示初始矩形个数和操作个数。

接下来 $N$ 行，第 $i$ 行包含五个整数 $l_i\ d_i\ r_i\ u_i\ w_i$，表示第 $i$ 个矩形的位置与权值。

接下来 $Q$ 行，每行描述一个操作：

• 0 l d r u w：添加一个权值为 $w$、位置为 $[l,r) \times [d,u)$ 的矩形；
• 1 x y：查询包含点 $(x,y)$ 的矩形权值之和。

【输出】

对每个 1 x y 的查询操作，输出一行一个整数，表示所有包含点 $(x,y)$ 的矩形的权值之和。

【输入样例】

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】

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

【输出样例2】

11
0
111
0
111
1000

【数据范围】

• $1 \leq N \leq 100000$
• $1 \leq Q \leq 100000$
• $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 l d r u w 操作：$0 \leq l < r \leq 10^9$，$0 \leq d < u \leq 10^9$，$0 \leq w \leq 10^9$
• 对于 1 x y 操作：$0 \leq x, y \leq 10^9$

【来源】

Library Checker（yosupo06） rectangle_add_point_get