你有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）。
2745: 计算矩形
时间限制: 1 Sec 内存限制: 128 MB提交: 0 解决: 1
[提交][状态][讨论版][命题人:]
题目描述
输入描述
输入的第一行包含一个整数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。
每个测试案例的第一行有两个整数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个查询的答案。
样例输入
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
样例输出
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。
来源
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
关于网站改版