像这样的一条线在图上扫描时,便是扫描线。
(呃呃和没说没有任何区别呢)
因此可见扫面线往往是求矩形面积并集或周长并集的好工具,当然,也可以运用在二维图中。
当然它不止可以从上往下扫,还可以从左往右扫:
(当然自己画的图可能丑一些,我解释一下,那个紫色的是扫描线)
如果说我们要求这个两个矩形的并面积怎么求?
当然你可能是直接容斥:\(S_1+S_2-S_1\timesS_2\)。
但是要是数据范围很大呢?多步容斥?你又不知道几个矩阵是不是都有交集。
这下不得不跟您谈一谈我们内存及其优秀的且很快的\(O(nlogn)\)算法了。
我们跟着例题说这个:
【模板】扫描线
题目描述
求\(n\)个四边平行于坐标轴的矩形的面积并。
输入格式
第一行一个正整数\(n\)。
接下来\(n\)行每行四个非负整数\(x_1,y_1,x_2,y_2\),表示一个矩形的四个端点坐标为\((x_1,y_1),(x_1,y_2),(x_2,y_2),(x_2,y_1)\)。
输出格式
一行一个正整数,表示\(n\)个矩形的并集覆盖的总面积。
样例#1
样例输入#1
2100100200200150150250255样例输出#1
18000提示
对于\(20\%\)的数据,\(1\len\le1000\)。对于\(100\%\)的数据,\(1\len\le{10}^5\),\(0\lex_1 怎么求这两个矩形的面积并? 求三个小矩形面积相加嘛。 怎么求这三个矩形的面积? 宽是两条扫描线的之间的\(x\)差值,长是求边嘛。 我们把每条扫描线与矩形边重合部分的左右端点记录一下,\(y\)轴高度记录一下就可以了: \(S=\)两条扫描线之间高度差\(\times\)扫描线覆盖长度 如何维护\(x\)长度? 毫无疑问,我们可以尝试用桶维护: 设四元组\((x_1,x_2,y,k)\)表示一条横线,其中\(k\)表示覆盖次数,我们将\(b_{x_1}\),\(b_{x_1}+1\),\(b_{x_1}+1\),……,\(b_{x_2}-1\)这些桶都加\(1\),表示覆盖了\([x_1,x_2]\)区间。 因此被覆盖的长度为\(\sum_{b_i>0}\limits(y_{i+1}-y_i)\)。 选择桶来维护扫描线上的\(x\)是否被覆盖,显然是有很多问题的: 什么什么什么,等等,线段树优化? 为什么能够线段树优化? 我们把每一条垂直于\(x\)轴的竖边提取出来,然后把他们延伸到\(x\)轴上,这不就把\(x\)轴分割成了线段? 因此,我们设\([l,r]\)就是我们需要维护的区间,需要维护: 但是,线段树有一个前提问题: 线段树存在长度为\(1\)的点,但是这个节点对应的应该是一个\(x\)坐标,也就是说,像这样的叶节点,却保留了两种信息,而我们需要维护的是扫描线上每一段被覆盖的次数及其长度。 而且我们早已确定的是,左右儿子没有交集,但是相邻的两个线段\([1,2]\)与\([2,3]\)显然存在了交集\(2\),我们必须考虑改变区间与横边的映射关系。 因此,我们选择将原本表示区间\([l,r]\)的节点表示区间\([l,r+1]\),这样就兼容了。 以下的\(x_i,y_i\)表示离散后坐标,\(val_{x_i},val{y_i}\)表示原值。 然后,我们统计线段树根节点的长度标记,乘两条横边之间高度差就得到了一部分的面积。 对于一个四元组\((x_1,x_2,y,k)\),我们在\((val_{y_1},val_{y_2}-1)\)上执行区间修改,该区间被划分为\(logN\)个节点,将这些节点的覆盖次数\(cnt\)都加\(1\)。 因此,对于线段树上任意一个节点\([l,r]\),若\(cnt>0\),则\(len=(r+1)-l\)。 (这里\(r\)与\(l\)都代表的是离散化后坐标) (这是坐标,所以不用在后面\(+1\)。) 否则,该点的\(len\)等于子节点\(len\)之和。 然而然而,如果我们遇到矩阵的上边,必须清空信息时,我们选择: 将矩形的上边的和下边的赋为相反的权值。 由于我们的扫描线是从下往上走的,那么完全可以将矩形的下边赋值为\(1\),给矩形的上边赋值为\(-1\),当我们遇到下边时,说明这个矩形还会在我们分割的多个小矩形部分出现,所以它对应的区间被覆盖的次数加\(1\),之后统计它的影响,当我们遇到一条上边,之前一定已经统计完下边的影响,应该将对应区间的覆盖次数\(-1\),此时该矩形面积统计完毕。 扫描线今年NOIT1考了? 好押 呃呃今天说扫描线思想,面积并是扫描线裸题。 InterestingSections 题面翻译 给你一个长为\(n\)的非负整数序列\(a\),求有多少区间\([l,r]\)满足\(\text{popcount}(\max\limits_{i=l}^ra_i)=\text{popcount}(\min\limits_{i=l}^ra_i)\)。 \(1\len\le10^6,0\lea_i\le10^{18}\)。 Thefirstlinecontainsasingleinteger$n$($1\len\le10^6$),thesizeofarray$a$. Thesecondlinecontains$n$integers$a_1,a_2,\dots,a_n$($0\lea_i\le10^{18}$),thecontentsofarray$a$. Outputasinglenumber—thetotalnumberofsegmentsthatpassedthecheck. 512345样例输出#1 9样例#2 样例输入#2 10057391016137样例输出#2 18(ps:某个数的popcount指某个数在二进制下\(1\)的总数) 就是给你一个长度为\(n\)的数组,要求输出该数组多少个区间的最大值和最小值的\(popcount\)是相等的。 那我们可以转换一下问题:给你一个长度为\(n\)的数组,问该数组有多少个区间的最大值最小值都在相同的\(popcount\)上。(也就是很多人题解写的“合适位置”) 这种区间带两个\(\sum\)的问题似乎都可以用扫描线或者\(CDQ\)分治来做。 (但是对于本题来说\(CDQ\)好像代码又短又快) (据说对于维护的东西越多,线段树就越优,反之\(CDQ\)就更优) 先枚举所有的\(popcount\)值,如果该区间最大值最小值都在我枚举的\(popcount\)值上,那赋为值\(1\)。 那就可以维护一个线段树,线段树每个节点表示当前\(l,r\)的每一个点为左端点,到现在扫到的\(i\)的\(popcount\)贡献。