题目 1416

矩形覆盖计数

查看题解 ↗GitHub ↗如何评测
题号
1416
时间限制
3000 ms
内存限制
256 MB
标签
数据结构树状数组扫描线
来源
ROJ 原创(配套 1415 矩形加点求和)

【题目描述】

二维平面上有 NN 个矩形,第 ii 个矩形覆盖区域为

[li,ri)×[di,ui)={(x,y)∈R2∣li≤x<ri, di≤y<ui}[l_i,r_i) \times [d_i,u_i) = \{(x,y)\in \mathbb{R}^2 \mid l_i\leq x < r_i,\ d_i \leq y < u_i\}

注意矩形是半开区间:左、下边界包含在矩形内,右、上边界不包含。

现在给定 MM 个询问点,对于每个点 (xj,yj)(x_j, y_j),求有多少个矩形覆盖该点。

【输入】

第一行包含两个整数 NN 和 MM,表示矩形个数和询问点个数。

接下来 NN 行,第 ii 行包含四个整数 li di ri uil_i\ d_i\ r_i\ u_i,表示第 ii 个矩形的位置。

接下来 MM 行,第 jj 行包含两个整数 xj yjx_j\ y_j,表示第 jj 个询问点的坐标。

【输出】

输出 MM 行,第 jj 行一个整数,表示覆盖第 jj 个询问点的矩形个数。

【输入样例】

文本
3 5
1 1 4 4
2 0 3 5
0 2 5 3
2 2
1 1
2 4
4 2
0 0

【输出样例】

文本
3
1
1
1
0

【输入样例2】

文本
2 3
0 0 10 10
0 0 10 10
5 5
10 10
0 0

【输出样例2】

文本
2
0
2

【数据范围】

  • 1≤N≤1000001 \leq N \leq 100000
  • 1≤M≤1000001 \leq M \leq 100000
  • 0≤li<ri≤1090 \leq l_i < r_i \leq 10^9
  • 0≤di<ui≤1090 \leq d_i < u_i \leq 10^9
  • 0≤xj,yj≤1090 \leq x_j, y_j \leq 10^9

【提示】

(x,y)(x, y) 被 [l,r)×[d,u)[l,r) \times [d,u) 覆盖,当且仅当 l≤x<rl \leq x < r 且 d≤y<ud \leq y < u。样例2 中 (10,10)(10,10) 恰好落在两个矩形的右、上边界上,不被任何矩形覆盖。

数据下载

题目 1416 的公开数据

正在读取文件列表…

常用命令

题目 1416 的 ROJ 命令

以下命令默认使用全局安装的 ROJ Skill,请在终端中直接执行;如果修改过 AGENT_HOME,请将命令中的 ~/.agents 替换为对应目录。