Home => ProblemSet => 3.2-50:[SHOI2007] 园丁的烦恼
Problem2003--3.2-50:[SHOI2007] 园丁的烦恼

2003: 3.2-50:[SHOI2007] 园丁的烦恼

Time Limit: 1 Sec  Memory Limit: 128 MB  Submit: 0  Solved: 0
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

国王的园丁非常聪明。国王打算测试他的实力: “年轻人,在我的花园里有 n 棵树,每一棵树可以用一个整数坐标来表示,一会儿,我的 m 个骑士们会来轮番询问你某一个矩阵内有多少树,如果你不能立即答对,你就准备走人吧!”说完,国王走了。
这下园丁傻眼了,他没有准备过这样的问题。所幸的是,作为“全国园丁保护联盟”的会长——你,可以成为他的最后一根救命稻草。

Input

第一行有两个整数 n,m,分别表示树木个数和询问次数。
接下来 n 行,每行两个整数 x,y,表示存在一棵坐标为 (x,y) 的树。有可能存在两棵树位于同一坐标。
接下来 m 行,每行四个整数 a,b,c,d,表示查询以 (a,b) 为左下角,(c,d) 为右上角的矩形内部(包括边界)有多少棵树。

Output

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

Sample Input Copy

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

Sample Output Copy

3

HINT

  • 对于 30% 的数据,保证 n,m≤10。
  • 对于 100% 的数据,保证 0≤n≤5×105,1≤m≤5×105,0≤x,y,a,b,c,d≤107,a≤c,b≤d。

Source/Category