#P6861. [2024年山东第二轮集训]第二题

    ID: 6692 传统题 3000ms 512MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>数据结构计算几何扫描线贪心CF2600分块ST表模拟

[2024年山东第二轮集训]第二题

第二题(dierti)

题目描述

平面上有 nn 个边平行于坐标轴的矩形,第 ii 个矩形的左下角为 (xai,yai)(xa_i,ya_i),右上角为 (xbi,ybi)(xb_i,yb_i)。

有 qq 次询问,每次给出 l,rl,r,求编号为 l,l+1,…,rl,l+1,\ldots,r 的所有矩形的并集面积。重叠部分只计一次。

本题的矩形坐标和询问区间按数据范围中规定的方式随机生成。

输入格式

第一行一个整数 testidtestid,表示测试点编号。

第二行两个整数 n,qn,q。

接下来 nn 行,每行四个整数 xai,yai,xbi,ybixa_i,ya_i,xb_i,yb_i,描述一个矩形。

接下来 qq 行,每行两个整数 l,rl,r,描述一次询问。

输出格式

输出 qq 行,每行一个整数,表示对应的矩形并集面积。

输入输出样例

见原题下发文件。

注意:第一个样例不符合坐标在 [1,109][1,10^9] 内随机的性质;其余样例的第一行 testidtestid 表示它符合哪个测试点的数据范围。

数据范围

所有数据满足 1≤n,q≤1051\le n,q\le10^5,1≤xai<xbi≤1091\le xa_i<xb_i\le10^9,1≤yai<ybi≤1091\le ya_i<yb_i\le10^9,1≤l≤r≤n1\le l\le r\le n。

随机方式如下。每个测试点有常数 X,YX,Y:

  • (xai,xbi)(xa_i,xb_i) 在所有满足 1≤a<b≤X1\le a<b\le X 的整数对 (a,b)(a,b) 中等概率随机选取。
  • (yai,ybi)(ya_i,yb_i) 在所有满足 1≤c<d≤Y1\le c<d\le Y 的整数对 (c,d)(c,d) 中等概率随机选取。
  • (l,r)(l,r) 在所有满足 1≤l≤r≤n1\le l\le r\le n 的整数对中等概率随机选取。

X,YX,Y 不会直接输入,可由 testidtestid 查下表确定。

测试点编号 nn 的上界 qq 的上界 XX YY
1∼21\sim2 100100 10910^9 10910^9
3∼63\sim6 10310^3
7∼97\sim9 10510^5 10510^5 22
10∼1310\sim13 10310^3 10910^9
14∼1714\sim17 6×1046\times10^4
18∼2018\sim20 10510^5