3199 - 【基础】矩形
题目描述
给出 n 个矩形，其中第 i个矩形的高为 hi，宽为 wi。现要处理 q 个查询请求，每个查询由 hs、ws、hb、wb 四个整数组成。
每次查询需从 n 个矩形中找出符合如下要求的矩形 s：高 hb 宽 wb 的矩形能容纳矩形 s，同时 s 能容纳高 hs 宽 ws 的矩形（如下图所示）。
试计算所有符合要求的 s 的面积总和。 注意:如果两个矩形具有相同的高度或宽度，那么它们就不能相互容纳。另外矩形不能旋转。
输入
第一行包含两个整数 n 和 q (1 \le n \le 10^3, 1 \le q \le 10^3)，表示矩形的数量和查询的次数。
接下来的 n 行每行包含两个整数 hi 和 wi (1 \le hi, wi \le 1000)，表示第 i 个矩形的高度和宽度。
接下来的 q 行每行包含四个整数 hs, ws, hb, wb (1 \le hs < hb \le 1000, 1 \le ws < wb \le 1000)，表示查询的高度范围 [hs, hb) 和宽度范围 [ws, wb)。
输出
一个整数，表示答案。
样例
输入
2 1 2 3 3 2 1 1 3 4
输出
6
输入
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
输出
41 9 0 54 4
输入
3 1 999 999 999 999 999 998 1 1 1000 1000
输出
2993004
说明
100\% 的数据
- 1 \leq n \leq 10^3
- 1 \leq q \leq 10^3
- 1 \leq h_i, w_i \leq 1000
对于样例 1 解释
我们需要找出所有能容纳 1 \ast 1 同时又能被 3 \ast 4 容纳的矩形的面积之和。只有 2 \ast 3 的矩形可以，因为 1 \le 3，所以 1 \ast 1 的矩形可以放入 2\ast 3 ；2 \le 3 且 3 \le 4 ，所以 2 * 3的矩形可以容纳 3 \ast 4。
3 \ast 2 的矩形虽然能容纳 1 \ast 1 的矩形；但太高，无法放入 3 \ast 4 的矩形中总面积为 2 \ast 3 = 6。
标签