← 返回题目列表

Codeforces · 1722/E

E. 计算矩形

中文机器翻译题面 查看原题

你有$$$n$$$个矩形,第$$$i$$$个矩形的高度为$$$h_i$$$,宽度为$$$w_i$$$。

系统会向您询问 $$$q$$$ 形式的查询 $$$h_s \ w_s \ h_b \ w_b$$$。

对于每个查询输出,您拥有的矩形的总面积可以适合高度为 $$$h_s$$$ 和宽度为 $$$w_s$$$ 的矩形,同时也适合高度为 $$$h_b$$$ 和宽度为 $$$w_b$$$ 的矩形。换句话说,打印 $$$\sum h_i \cdot w_i$$$ 对于 $$$i$$$,使得 $$$h_s < h_i < h_b$$$ 和 $$$w_s < w_i < w_b$$$。

请注意,如果两个矩形具有相同的高度或相同的宽度,那么它们就无法相互装入。另请注意,您无法旋转矩形。

请注意,某些测试用例的答案不适合 32 位整数类型,因此您应该在编程语言中至少使用 64 位整数类型(例如 C++ 的 long long)。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。

每个测试用例的第一行两个整数 $$$n, q$$$ ($$$1 \leq n \leq 10^5$$$; $$$1 \leq q \leq 10^5$$$) - 您拥有的矩形数量和查询数量。

接下来是 $$$n$$$ 行,每行包含两个整数 $$$h_i, w_i$$$ ($$$1 \leq h_i, w_i \leq 1000$$$) — 第 $$$i$$$ 个矩形的高度和宽度。

接下来是 $$$q$$$ 行,每行包含四个整数 $$$h_s, w_s, h_b, w_b$$$ ($$$1 \leq h_s < h_b,\ w_s < w_b \leq 1000$$$) - 每个查询的描述。

所有测试用例的 $$$q$$$ 总和不超过 $$$10^5$$$,所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出 $$$q$$$ 行,第 $$$i$$$ 行包含第 $$$i$$$ 查询的答案。

示例

输入 #1

3
2 1
2 3
3 2
1 1 3 4
5 5
1 1
2 2
3 3
4 4
5 5
3 3 6 6
2 1 4 5
1 1 2 10
1 1 100 100
1 1 3 3
3 1
999 999
999 999
999 998
1 1 1000 1000

输出 #1

6
41
9
0
54
4
2993004

注意

在第一个测试用例中,只有一个查询。我们需要找到可以容纳 $$$1 \times 1$$$ 矩形并容纳 $$$3 \times 4$$$ 矩形的所有矩形的面积总和。

只有 $$$2 \times 3$$$ 矩形有效,因为 $$$1 < 2$$$ (比较高度)和 $$$1 < 3$$$ (比较宽度),因此 $$$1 \times 1$$$ 矩形适合内部,而 $$$2 < 3$$$ (比较高度)和 $$$3 < 4$$$ (比较宽度)宽度),因此它适合 $$$3 \times 4$$$ 矩形。 $$$3 \times 2$$$ 矩形太高,无法放入 $$$3 \times 4$$$ 矩形中。总面积为 $$$2 \cdot 3 = 6$$$。