CF1722E Counting Rectangles

你有 $n$ 个矩形，第 $i$ 个矩形的高为 $h_i$，宽为 $w_i$。 你将会被询问 $q$ 次，每次询问的形式为 $h_s\ w_s\ h_b\ w_b$。 对于每个询问，输出你拥有的所有矩形中，能够容纳一个高为 $h_s$、宽为 $w_s$ 的矩形，并且也能被一个高为 $h_b$、宽为 $w_b$ 的矩形容纳的所有矩形的面积之和。换句话说，输出所有满足 $h_s < h_i < h_b$ 且 $w_s < w_i < w_b$ 的 $i$ 的 $\sum h_i \cdot w_i$。 请注意，如果两个矩形有相同的高或宽，则它们不能互相容纳。另外，矩形不能旋转。 还要注意，对于某些测试点，答案可能无法用 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 \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$。 由 ChatGPT 4.1 翻译