学习笔记扫描线Sonnety

像这样的一条线在图上扫描时,便是扫描线。

(呃呃和没说没有任何区别呢)

因此可见扫面线往往是求矩形面积并集或周长并集的好工具,当然,也可以运用在二维图中。

当然它不止可以从上往下扫,还可以从左往右扫:

(当然自己画的图可能丑一些,我解释一下,那个紫色的是扫描线)

如果说我们要求这个两个矩形的并面积怎么求?

当然你可能是直接容斥:\(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\)贡献。

THE END
1.线上学习的作文(通用23篇)在平凡的学习、工作、生活中,大家都不可避免地会接触到作文吧,通过作文可以把我们那些零零散散的思想,聚集在一块。相信许多人会觉得作文很难写吧,以下是小编为大家收集的线上学习的作文,希望能够帮助到大家。 线上学习的作文 篇1 因为疫情我们被隔离在家里,所以今天我给你们讲一讲我的线上学习生活。 https://www.unjs.com/zuowendaquan/xuexizuowen/3414078.html
2.线上学习心得15篇线上学习心得1 深度的学习是以高级思维的发展和实际问题的解决为目的,以整合课程的'知识为内容,积极主动地,批判地学习新的知识和思维,并将它们融入原有的认知结构中且将已有的知识迁移到新的情景中的一种学习。 首先我们要明确目标:要在五大领域全面发展的基础上培养内在辛福、外在优秀、面向未来、全面发展的现代化https://www.cnfla.com/xindetihui/2733145.html
3.关于线上学习的作文(精选27篇)在学习、工作、生活中,大家总少不了接触作文吧,写作文可以锻炼我们的独处习惯,让自己的心静下来,思考自己未来的方向。你知道作文怎样写才规范吗?以下是小编为大家整理的线上学习的作文,仅供参考,大家一起来看看吧。 线上学习的作文 篇1 因为疫情我们被隔离在家里,所以今天我给你们讲一讲我的线上学习生活。 https://www.ruiwen.com/zuowen/xuexi/5578839.html
4.我的线上学习优秀作文(通用23篇)我的线上学习优秀作文(通用23篇) 在学习、工作乃至生活中,大家总免不了要接触或使用作文吧,作文根据体裁的不同可以分为记叙文、说明文、应用文、议论文。相信许多人会觉得作文很难写吧,以下是小编为大家整理的我的线上学习优秀作文,欢迎阅读与收藏。 https://www.fwsir.com/fanwen/html/fanwen_20200602171647_424054.html
5.线上学习心得体会作文(精选4篇)最后,我觉得我们应该珍惜这段时间,做到日日精进,停课不停学。如荀子所说,学不可以已,学习是没有止境的,未能返校的这段时间,我们可以提升自己,感悟人生!无论是线上学习还是线下授课,都是在传播知识,只是方式不同而已,我们都应该认真对待,上好每一节课。 https://www.360wenmi.com/f/fileq73q09l4.html
6.线上学习心得体会(通用17篇)线上学习心得体会 2 线上学习和线下学习是不同的概念,一个是积极参与,一个是自己主动去学好,如果自己不认真努力不细心坚持是学不好的,这次的网课充分让我知道了线上学习的优点。 线上学习能够非常容易的就解决线下辅导的问题,在平时遇到一个问题,或者几个问题,我们不会。不同的同学去询问,老师需要重复多遍,但是https://www.wenshubang.com/xindetihui/3345434.html
7.学生线上反思模板范文【学生姓名】 【班级】 【日期】 一、前言 随着科技的飞速发展,线上学习已成为当下教育的新趋势。在这段时间的线上学习中,我收获颇丰,同时也意识到自己在学习过程中存在的问题。为了更好地提升自己,现将我在线上学习期间的反思总结如下。 二、线上学习收获 1. 自律能力的提升:线上学习要求我自觉遵守学习计划,https://wenku.baidu.com/view/83ed2ddef76527d3240c844769eae009581ba2fc.html
8.计算机毕业设计线上学习平台系统大学生线上学习系统毕业设计本次开发的线上学习平台系统实现了字典管理、试卷表管理、试题表管理、考试记录表管理、答题详情表管理、错题表管理、论坛管理、公告信息管理、课程管理、课程收藏管理、课程留言管理、视频管理、视频收藏管理、视频留言管理、视频观看记录管理、用户管理、管理员管理等功能。系统用到了关系型数据库中王者MySql作为系统的https://blog.csdn.net/2301_79554433/article/details/136072068
9.线上教学大家谈浅谈如何在《大学英语》线上课堂中开展学生如果学生没有在过去的学习中养成独立、专注、持续的自主学习习惯,没有同伴和老师的监督和指导,线上学习的效果很难保证。因此,老师有必要在线上教学的过程中给学生创造合作学习的机会,实现学生与学生之间的良性互动。我从以下几方面谈一下自己的做法: 一、营造氛围,早做准备https://jwc.hbu.edu.cn/info/1109/3859.htm
10.在传智线上学习的一天带你体验传智播客线上教学全方位保障【在传智线上学习的一天】带你体验传智播客线上教学全方位保障更新时间:2020年02月18日15时56分 来源:传智播客 浏览次数: 点击视频,7分钟带你体验传智播客线上教学全方位保障上一篇:十大IT热门学科在线直播体验课正式来袭,全免费!!! 下一篇:传智播客无缝切换线上教学,凭什么?https://www.itcast.cn/news/20200218/15565087538.shtml
11.中国研究生招生信息网温州肯恩大学校园开放日预告| 12月1日,在温肯遇见 香港大学经管学院硕士课程—线上公开课11月19至22日 江苏海洋大学我校召开研究生招生工作领导小组会议 杭州师范大学2025年博士研究生招生日程安排 2025年深圳大学中外合作办学项目金融科技与风险控制硕士招生简章 考研资讯 复试备考 2025年研考学情调研 2025研https://yz.chsi.com.cn/
12.(一)学习内容:1.线上学习要求:线上视频全部看完。有问题在【简答题】 (一) 学习内容: 1. 线上学习 要求:线上视频全部看完。 有问题在学习通交流。 2. 线下学习:(选择你上课用的习题集和教材版本) 完成习题集练习和教材相关内容的学习 (1)工程图学基础教程第3版习题集:P58-P109 (2)画法几何与机械制图第2版习题集:P88-P157 (3)对应教材的相关内容 (二)暂定https://www.shuashuati.com/ti/cdcfbcc3102c4a45bfe3386141fcb779.html
13.政策解读关于指定在道路上学习驾驶机动车路线时间的通告的申请人为自学直考人员的,在道路上学习驾驶时,应当在自学用车上按规定放置、粘贴学车专用标识,自学用车不得搭载随车指导人员以外的其他人员。 二、学习驾驶其他车型的路线、时间 (一)无轨电车: 一号线,中山八路全路段、中山七路全路段、中山六路全路段、解放中路(中山六路路口至惠福西路路口路段)、惠福西路(解放中https://www.gz.gov.cn/zwgk/zcjd/zcjd/content/post_8224312.html
14.学习线上线下学习机会推荐,欢迎分享给需要的食品人会展动态近期线上学习机会推荐: 【免费】消毒产品及化妆品备案 6月22日 14:30-16:00 (青岛科创质量检测有限公司) 报名和听课地址:http://study.foodmate.net/web/zbk/detail?id=285&fuid=62 主讲人:丁婧 中国海洋大学海洋生命学院 生物工程硕士。主要从事化妆品、消毒产品、食品、医疗器械的行政许可、设计开发与注册备案https://www.foodmate.net/news/quanwei/2020/06/564479.html
15.学习“四史”中国共产党历史上的五次统一战线巩固和发展爱国统一战线,对于把中华儿女广泛团结起来,投身决胜全面建成小康社会、开启全面建设社会主义现代化国家新征程的伟大实践,聚合起实现中华民族伟大复兴中国梦的磅礴力量,具有十分重要的意义。 文章来源:《学习时报》微信公众号 原标题:《【学习“四史”】中国共产党历史上的五次统一战线》https://www.thepaper.cn/newsDetail_forward_8949199
16.在线教学吴宪玲:以促进学生学习为中心,精心打造翻转课堂2020年,在这新的—年中,中国人过了一个不一样的春节,而所有教师和学生们都过了一个不一样的寒假。3月2日本是我们的开学日,因为疫情,开学延期。为响应国家教育部、省教育厅在防疫期间学生在家能够”停课不停学“的号召,我们要开始开展线上教学,并且确保学生线上学习学有所获,学有所成。对于从未涉足过的“线https://jkyhlx.qqhrit.com/info/1070/6048.htm
17.中山火炬职业技术学院网络教学线上战“疫”(六)冯嫦:功夫在“今天,我和大家一起来学习《工业自动化控制技术》的新章节···”温和亲切的面庞、娓娓道来的讲授,观看冯嫦老师的网络课程,扑面而来的是她自信的风采。这种自信来源于她对教学内容的熟练掌握和线上教学节奏的精准把控。 01 时刻准备着 线上教学是“功夫在诗外” 疫情当前https://static.nfapp.southcn.com/content/202003/06/c3217164.html