第二题(dierti)
题目描述
平面上有 n 个边平行于坐标轴的矩形,第 i 个矩形的左下角为 (xai,yai),右上角为 (xbi,ybi)。
有 q 次询问,每次给出 l,r,求编号为 l,l+1,…,r 的所有矩形的并集面积。重叠部分只计一次。
本题的矩形坐标和询问区间按数据范围中规定的方式随机生成。
输入格式
第一行一个整数 testid,表示测试点编号。
第二行两个整数 n,q。
接下来 n 行,每行四个整数 xai,yai,xbi,ybi,描述一个矩形。
接下来 q 行,每行两个整数 l,r,描述一次询问。
输出格式
输出 q 行,每行一个整数,表示对应的矩形并集面积。
输入输出样例
见原题下发文件。
注意:第一个样例不符合坐标在 [1,109] 内随机的性质;其余样例的第一行 testid 表示它符合哪个测试点的数据范围。
数据范围
所有数据满足 1≤n,q≤105,1≤xai<xbi≤109,1≤yai<ybi≤109,1≤l≤r≤n。
随机方式如下。每个测试点有常数 X,Y:
- (xai,xbi) 在所有满足 1≤a<b≤X 的整数对 (a,b) 中等概率随机选取。
- (yai,ybi) 在所有满足 1≤c<d≤Y 的整数对 (c,d) 中等概率随机选取。
- (l,r) 在所有满足 1≤l≤r≤n 的整数对中等概率随机选取。
X,Y 不会直接输入,可由 testid 查下表确定。
| 测试点编号 |
n 的上界 |
q 的上界 |
X |
Y |
| 1∼2 |
100 |
109 |
109 |
| 3∼6 |
103 |
| 7∼9 |
105 |
105 |
2 |
| 10∼13 |
103 |
109 |
| 14∼17 |
6×104 |
| 18∼20 |
105 |