像这样的一条线在图上扫描时，便是扫描线。
（呃呃和没说没有任何区别呢）
因此可见扫面线往往是求矩形面积并集或周长并集的好工具，当然，也可以运用在二维图中。
当然它不止可以从上往下扫，还可以从左往右扫：
（当然自己画的图可能丑一些，我解释一下，那个紫色的是扫描线）
如果说我们要求这个两个矩形的并面积怎么求？
当然你可能是直接容斥：\(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\)贡献。