time limit per test
6 seconds
memory limit per test
256 megabytes
You have nn rectangles, the ii-th rectangle has height hihi and width wiwi.
You are asked qq queries of the form hs ws hb wbhs ws hb wb.
For each query output, the total area of rectangles you own that can fit a rectangle of height hshs and width wsws while also fitting in a rectangle of height hbhb and width wbwb. In other words, print ∑hi⋅wi∑hi⋅wi for ii such that hs<hi<hbhs<hi<hb and ws<wi<wbws<wi<wb.
Please note, that if two rectangles have the same height or the same width, then they cannot fit inside each other. Also note that you cannot rotate rectangles.
Please note that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).
Input
The first line of the input contains an integer tt (1≤t≤1001≤t≤100) — the number of test cases.
The first line of each test case two integers n,qn,q (1≤n≤1051≤n≤105; 1≤q≤1051≤q≤105) — the number of rectangles you own and the number of queries.
Then nn lines follow, each containing two integers hi,wihi,wi (1≤hi,wi≤10001≤hi,wi≤1000) — the height and width of the ii-th rectangle.
Then qq lines follow, each containing four integers hs,ws,hb,wbhs,ws,hb,wb (1≤hs<hb, ws<wb≤10001≤hs<hb, ws<wb≤1000) — the description of each query.
The sum of qq over all test cases does not exceed 105105, and the sum of nn over all test cases does not exceed 105105.
Output
For each test case, output qq lines, the ii-th line containing the answer to the ii-th query.
Example
Input
Copy
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
Output
Copy
6 41 9 0 54 4 2993004
Note
In the first test case, there is only one query. We need to find the sum of areas of all rectangles that can fit a 1×11×1 rectangle inside of it and fit into a 3×43×4 rectangle.
Only the 2×32×3 rectangle works, because 1<21<2 (comparing heights) and 1<31<3 (comparing widths), so the 1×11×1 rectangle fits inside, and 2<32<3 (comparing heights) and 3<43<4 (comparing widths), so it fits inside the 3×43×4 rectangle. The 3×23×2 rectangle is too tall to fit in a 3×43×4 rectangle. The total area is 2⋅3=62⋅3=6.
每个测试的时间限制为 6 秒
每个测试的内存限制为 256 兆字节
您有 n
个矩形，第 i 个矩形的高度为 hi
，宽度为 wi
。
您需要提出 q
个查询，形式为 hs ws hb wb
。
对于每个查询输出，您拥有的矩形的总面积可以容纳高度为 hs
，宽度为 ws
的矩形，同时也可以容纳高度为 hb
，宽度为 wb
的矩形。换句话说，打印 i
的 ∑hi⋅wi
，使得 hs<hi<hb
和 ws<wi<wb
。
请注意，如果两个矩形具有相同的高度或相同的宽度，则它们不能相互容纳。还请注意，您不能旋转矩形。
请注意，某些测试用例的答案不适合 32 位整数类型，因此您应该在编程语言中使用至少 64 位整数类型（例如 C++ 的 long long）。
输入
输入的第一行包含一个整数 t
(1≤t≤100
) — 测试用例的数量。
每个测试用例的第一行两个整数 n,q
(1≤n≤105
; 1≤q≤105
) — 您所拥有的矩形数量和查询数量。
接下来是 n
行，每行包含两个整数 hi,wi
(1≤hi,wi≤1000
) — 第 i
个矩形的高度和宽度。
接下来是 q
行，每行包含四个整数 hs,ws,hb,wb
(1≤hs<hb, ws<wb≤1000
) — 每个查询的描述。
所有测试用例的 q
之和不超过 105
，所有测试用例的 n
之和不超过 105
。
输出
对于每个测试用例，输出 q
行，第 i
行包含第 i
个查询的答案。
示例
InputCopy
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
OutputCopy
6
41
9
0
54
4
2993004
注意
在第一个测试用例中，只有一个查询。我们需要求出所有能容纳 1×1
矩形并能放入 3×4
矩形的矩形面积之和。
只有 2×3
矩形可行，因为 1<2
（比较高度）和 1<3
（比较宽度），所以 1×1
矩形适合放入其中，而 2<3
（比较高度）和 3<4
（比较宽度），所以它适合放入 3×4
矩形。3×2
矩形太高，无法放入 3×4
矩形。总面积为 2⋅3=6
。
代码：
#include <iostream>
#include <vector>
using namespace std;
const int MAX_DIM = 1000;
void solve() {
int t;
cin >> t;
while (t--) {
int n, q;
cin >> n >> q;
vector<vector<long long>> prefix(MAX_DIM + 1, vector<long long>(MAX_DIM + 1, 0));
for (int i = 0; i < n; ++i) {
int h, w;
cin >> h >> w;
prefix[h][w] += 1LL * h * w;
}
for (int h = 1; h <= MAX_DIM; ++h) {
for (int w = 1; w <= MAX_DIM; ++w) {
prefix[h][w] += prefix[h - 1][w] + prefix[h][w - 1] - prefix[h - 1][w - 1];
}
}
while (q--) {
int hs, ws, hb, wb;
cin >> hs >> ws >> hb >> wb;
long long total_area = prefix[hb - 1][wb - 1]
- prefix[hs][wb - 1]
- prefix[hb - 1][ws]
+ prefix[hs][ws];
cout << total_area << endl;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}