【题目描述】
二维平面上有 N 个矩形,第 i 个矩形覆盖区域为
[li,ri)×[di,ui)={(x,y)∈R2∣li≤x<ri, di≤y<ui}注意矩形是半开区间:左、下边界包含在矩形内,右、上边界不包含。
现在给定 M 个询问点,对于每个点 (xj,yj),求有多少个矩形覆盖该点。
【输入】
第一行包含两个整数 N 和 M,表示矩形个数和询问点个数。
接下来 N 行,第 i 行包含四个整数 li di ri ui,表示第 i 个矩形的位置。
接下来 M 行,第 j 行包含两个整数 xj yj,表示第 j 个询问点的坐标。
【输出】
输出 M 行,第 j 行一个整数,表示覆盖第 j 个询问点的矩形个数。
【输入样例】
文本
3 5
1 1 4 4
2 0 3 5
0 2 5 3
2 2
1 1
2 4
4 2
0 0
【输出样例】
【输入样例2】
文本
2 3
0 0 10 10
0 0 10 10
5 5
10 10
0 0
【输出样例2】
【数据范围】
- 1≤N≤100000
- 1≤M≤100000
- 0≤li<ri≤109
- 0≤di<ui≤109
- 0≤xj,yj≤109
【提示】
(x,y) 被 [l,r)×[d,u) 覆盖,当且仅当 l≤x<r 且 d≤y<u。样例2 中 (10,10) 恰好落在两个矩形的右、上边界上,不被任何矩形覆盖。