#P2163. [SHOI2007] 园丁的烦恼

    ID: 47 远端评测题 1000ms 125MiB 尝试: 2 已通过: 2 难度: 10 上传者: 标签>搜索2007各省省选树状数组离散化上海

[SHOI2007] 园丁的烦恼

题目背景

很久很久以前,在遥远的大陆上有一个美丽的国家。统治着这个美丽国家的国王是一个园艺爱好者,在他的皇家花园里种植着各种奇花异草。

有一天国王漫步在花园里,若有所思,他问一个园丁道: “最近我在思索一个问题,如果我们把花坛摆成六个六角形,那么……”

“那么本质上它是一个深度优先搜索,陛下。”园丁深深地向国王鞠了一躬。

“嗯……我听说有一种怪物叫九头蛇,它非常贪吃苹果树……”

“是的,显然这是一道经典的动态规划题,早在 N 元 40024002 年我们就已经发现了其中的奥秘了,陛下。”

“该死的,你究竟是什么来头?”

“陛下息怒,干我们的这行经常莫名其妙地被问到和 OI 有关的题目,我也是为了预防万一啊!” 王者的尊严受到了伤害,这是不可容忍的。

题目描述

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

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

输入格式

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

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

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

输出格式

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

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

3

提示

数据规模与约定

  • 对于 30%30\% 的数据,保证 n,m10n, m \leq 10
  • 对于 100%100\% 的数据,保证 0n5×1050 \leq n \leq 5 \times 10^51m5×1051 \leq m \leq 5 \times 10^50x,y,a,b,c,d1070 \leq x, y, a, b, c, d \leq 10^7aca \leq cbdb \leq d