扫描线模板题

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

在一个 $W\times W$ 的整数点阵上，每个点的初始权值均为 $0$。

先进行 $n$ 次修改。每次给定一个闭矩形 $[x_1,x_2]\times[y_1,y_2]$ 和整数 $v$，把矩形内每个整数点的权值都增加 $v$。

全部修改完成后进行 $q$ 次查询。每次给定一个闭矩形，求其中所有整数点的权值之和。

输入格式

第一行三个整数 $n,q,W$。

接下来 $n$ 行，每行五个整数 $x_1,y_1,x_2,y_2,v$，描述一次修改。

接下来 $q$ 行，每行四个整数 $x_1,y_1,x_2,y_2$，描述一次查询。

输出格式

输出 $q$ 行，每行一个整数，依次表示各次查询的答案。

样例输入 1

5 5 5
3 1 3 5 3
2 1 4 5 4
5 1 5 2 -2
1 4 2 5 5
2 2 4 5 -2
1 3 4 4
2 2 5 4
1 5 2 5
3 1 4 3
1 2 4 5

样例输出 1

28
30
12
25
56

样例输入 2

5 5 5
4 1 4 1 1
3 1 4 1 -5
2 5 5 5 -2
2 1 5 1 4
2 1 4 3 2
4 4 4 5
2 1 4 1
1 4 2 5
1 1 3 5
2 2 5 3

样例输出 2

-2
9
-2
11
12

数据范围

对于所有数据：$1\le n,q,W\le 10^5$，$1\le x_1\le x_2\le W$，$1\le y_1\le y_2\le W$，$|v|\le 1000$。