50 #P1641. *【二分】点和矩形

*【二分】点和矩形

【题意】

在一个直角坐标系中,给出N个矩形(边平行于坐标轴,且矩形面积不为零)和M个点,问每个点在多少个矩形的内部(恰好在线上也算)。

【输入格式】

第一行两个整数 N M (1N10000,1M20000)N \ M \ (1 \le N \le 10000, 1 \le M \le 20000)

下来 NN 行,每行四个整数 x1 y1 x2 y2x_1 \ y_1 \ x_2 \ y_2 表示一个矩形的对角两点坐标 (105x1 y1 x2 y2105) (-10^5 \le x_1 \ y_1 \ x_2 \ y_2 \le 10^5)

下来 MM 对整数 (xi,yi)(x_i,y_i) ,每对整数表示一个点(105xi,yi105-10^5 \le x_i,y_i \le 10^5)。

注意:本题数据已更正,所以就算暴力不二分也稍稍优化一下例如排个序。

【输出格式】

MM 行,每行一个正整数,表示第 ii 个点在多少个矩形内。

【样例输入】

2 4
1 1 -10 -10
1 1 10 10
1 1
-12 543
3 6
-2 -3

【样例输出】

2
0
1
1