6001 - NOI:离线CDQ分治:[SHOI2007] 园丁的烦恼(二维偏序 )

通过次数

3

提交次数

15

时间限制 : 2 秒
内存限制 : 256 MB

看来一般的难题是难不倒这位园丁的,国王最后打算用车轮战来消耗他的实力: “年轻人,在我的花园里有 n 棵树,每一棵树可以用一个整数坐标来表示,一会儿,我的 m 个骑士们会来轮番询问你某一个矩阵内有多少树,如果你不能立即答对,你就准备走人吧!”说完,国王气呼呼地先走了。

这下轮到园丁傻眼了,他没有准备过这样的问题。所幸的是,作为“全国园丁保护联盟”的会长——你,可以成为他的最后一根救命稻草。

输入

第一行有两个整数 n, m,分别表示树木个数和询问次数。

接下来 n 行,每行两个整数 x, y,表示存在一棵坐标为 (x, y) 的树。有可能存在两棵树位于同一坐标。

接下来 m 行,每行四个整数 a, b, c, d,表示查询以 (a, b) 为左下角,(c, d) 为右上角的矩形内部(包括边界)有多少棵树。

输出

对于每个查询,输出一行一个整数表示答案。

样例

输入

3 1
0 0 
0 1
1 0
0 0 1 1

输出

3

提示

  • 对于 30\% 的数据,保证 n, m \leq 10
  • 对于 100\% 的数据,保证 0 \leq n \leq 5 \times 10^51 \leq m \leq 5 \times 10^50 \leq x, y, a, b, c, d \leq 10^7a \leq cb \leq d