扫描线
扫描线
扫描线 应用：一般用于计算多个矩形的总面积(重叠算一次)、总周长、最大重叠区域权值等问题。 总结： 运用线段树来实现。 计算多个矩形的总面积(重叠算一次)，虽然是区间修改，但是由于我们不用更新到子树上，所以不需要\(pushdown\). 最大重叠区域权值问题，一般需要需要基本转化，比如从二维数点问 ......
扫描线
AcWing 247. 亚特兰蒂斯 题意：给定若干个矩形（长宽均平行于坐标轴），求它们的面积并（矩形的顶点坐标可以是实数）。 本题是扫描线算法的模板题。 扫描线，顾名思义，就是按照一条线扫过去，对于本题 扫描线 - OI Wiki (oi-wiki.org) 如上图，这就是扫描线的过程。 发现按照线 ......
【模板】扫描线
【模板】扫描线 题目描述 求 $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, ......
搬运的 对于维护双半群信息以及扫描线问题的整理？
本来想写点技巧，但感觉这个东西就只能拿复合函数分析一下或者矩阵分析，所以这玩意感觉真没啥技巧。 注：不建议作为学习文章，仅为个人的整理笔记。 突然发现这种双半群信息维护用线段树貌似常数很大，出题人会把时间和数据范围开的很松。如果码力智商不够可以考虑更易理解且有时候更好写的分块做法。 CatOJ C0 ......
浅谈扫描线
Preface 本文部分题目摘自 lxl 的数据结构系列课件 由于工程量巨大，难免会出现错字、漏字的情况，如果影响到了您的阅读体验，还请私信我，我会在第一时间修复。 本文建议大家有一定的数据结构基础后再来阅读 /heart。 个人感觉扫描线不是难点，难点在于怎么抽象模型。 首先需要明白一个东西，叫做 ......
扫描线
假设有一条扫描线从一个图形的下方扫向上方（或者左方扫到右方），那么通过分析扫描线被图形截得的线段就能获得所要的结果。该过程可以用线段树进行加速。 P5490 【模板】扫描线 扫描线可以处理两类问题 一类是面积并 一类是周长并 #include<iostream> #include<algorithm ......
2021 CCPC 桂林 J 后缀数组+扫描线
原题链接 设字符串长度为n，下标从1开始。后缀数组进行排序后，对每个后缀i，它能贡献的不同的字串就是该后缀从\(ht_i+1\)到结尾\(n-sa_i+1\)的所有前缀,利用差分和前缀和预处理出长度小于等于i的子串贡献出的不同字串\(sum_i\)，对每次查询k，可以二分找到它所在长度\(len_k ......
Auguryの扫描线分享
Auguryの扫描线分享 扫描线是啥 有时候答案是不好计算的，但是答案可以拆分成多个段分别计算，且段与段之间可以快速转换，我们就可以用扫描线解决。 或者说，一个二维问题，我们可以用扫描线变成一维。 前置芝士 线段树、值域线段树、树状数组（胡扬好闪，拜谢胡扬） 离散化 现在我们有一堆数，你要处理与这堆 ......
扫描线面积并的牛子线段树
利用到的是，一条线段，只会出现两次。 那么，显然两次在线段树上遍历的节点是一样的，因此，我们可以直接修改定义，\(sum[cur]\) 表示线段树上的节点被多少条线段遍历到了，如果 \(sum[cur]>0\)，显然 \(cur\) 的贡献即区间长度，否则呢？否则，我们不需要考虑更大的区间，因为更大 ......
写个扫描线吧
虽然扫描线很简单，但是我发现理解还是有些不清晰，于是决定写一篇。原问题，或者说是例题 一个不好暴力东西，暴力模拟不带优化至少O（n^3）也是一个非常经典的线段树例题（因为懒得画图所以下面就直接用网上dalao的题解里面的图片了）首先，因为我们要在线段树上面记录下来每一个起始点和结束点，所以离散化是必 ......
扫描线
#include<bits/stdc++.h> #define maxn 200005 #define int long long using namespace std; int x[maxn];//x[i]表示从左往右第i条竖边 int tsum[maxn<<3],tlen[maxn<<3]; ......
扫描线算法
[TOC] # 扫描线 **扫描线**：假设有一条**竖直**的直线，从平面的最**左端**扫描到最**右端**，在扫描的过程中，直线上的一些线段会被给定的矩形覆盖。如果我们将这些覆盖的线段长度进行积分，就可以得到矩形的面积之和。  2.扫描线的板子没有`pushdown` ......
扫描线求 面积并 和 周长并
### 前言： 扫描线和正常线段树还是有区别的，我一开始直接自己码根本不会。 推荐： * 扫描线求面积并：[不分解的AgOH](https://www.bilibili.com/video/BV144411Z7tx/?spm_id_from=333.999.0.0) 、 [第454篇洛谷日报](ht ......
P5490 【模板】扫描线
###[$P5490$ 【模板】扫描线](https://www.luogu.com.cn/problem/P5490) ### 一、题目描述 求 $n$ 个四边平行于坐标轴的矩形的面积并。 #### 输入格式 第一行一个正整数 $n$。 接下来 $n$ 行每行四个非负整数 $x_1, y_1, x ......
【单调队列】 单调队列的“扫描线”理解
#【单调队列】 单调队列的“扫描线”理解 **“如果一个选手比你小还比你强，你就可以退役了。”——单调队列的原理** - 比你强，而且比你影响时间更长。 - 某种意义上，数学思维是生活中的思考的延伸。 [算法学习笔记(66): 单调队列](https://zhuanlan.zhihu.com/p/3 ......
扫描线
求矩形面积并，把矩阵竖着割开，累加。 矩形 $(x_1,y_1,x_2,y_2)$ 分成 $(x1,y1,y2,1)$ 和 $(x2,y1,y2,-1)$ 两条线，指的是，$x=x_i(y_1\leq x\leq y_2)$ 这样的线，土 $1$ 指的是加上或减去。 需要离散 flower，主要是 ......
扫描线学习笔记
## 0. 写在前面 扫描线好闪，拜谢扫描线 ## 1. 问题的引入 在一个二维的坐标系上，给出多个矩形，求他们的面积并 ## 2. 问题的分析 假设我们有这么一张图 ](https://www.luogu.c ......
[Ynoi2012] NOIP2015 充满了希望(扫描线+线段树)
### [题目传送门](https://www.luogu.com.cn/problem/P5524) ## solution 简单题。 我们正着做扫描线。 设 $t_i$ 表示位置 $i$ 最后一次进行二操作的时间，那么一操作就是交换 $t_x,t_y$ ，二操作就是区间复制。 对于三操作，开一个 ......
[Ynoi Easy Round 2021] TEST_152(颜色段数均摊+扫描线)
### [题目传送门](https://www.luogu.com.cn/problem/P8512) ## solution 简单题，考虑正着做扫描线，维护最后一次覆盖每个位置的修改时间，这个可以用 $set$ 维护颜色段数均摊。 那么显然对于一个以当前位置为右端点的询问，其答案就是所有最后修改时 ......
【学习笔记】扫描线
扫描线是用来求解图形面积并的一个算法。 # 问题引入 给定 $n$ 个长方形，求它们的面积并。下面以两个长方形为例：  （图片来源：oiwiki） 像这样的一条线在图上扫描 ......
扫描线Manhattan Distance
# Problem C. Manhattan Distance 主要算法：扫描线 二分 来源： XIII Samara Regional Intercollegiate Programming Contest Russia, Samara, March 29, 2020 >题意 ：给你二维平面上的n ......
扫描线小复习
## 扫描线 [toc] ### 思想 扫描线的思想十分简单，就是把矩形分为多次小的矩形求解罢了，关键在于实现 记得有一次周考就写挂了...... ### 实现 首先想要正好不重不漏地扫过一个矩形（只有一个的情况下）而不影响其他非矩形地方的方法是什么？ 假设我扫描线是从下往上扫的，那么对于这个矩形而 ......
扫描线 - 知识点梳理
扫描线算法可解决平面内平行坐标轴的线段有关的问题，例如求平面上平行于坐标轴的矩形的面积并，其原理在于模拟一条扫描线从下往上扫描。线段树是一种灵活的 Leafy Tree，可以灵活地扫描线上统计线段的分布情况，将一部分信息储存在分支节点上，另一部分信息下传至叶子节点，因此线段树是扫描线算法的核心。 # ......
扫描线
>* 扫描线能做什么？ >* 扫描线实际上是一种**思想**，而不是一种数据结构，它是一种**离线算法**，他将**事件点按照某种由你规定的顺序执行**后得到答案，一般需要**线段树或者树状数组**维护，同时有时也需要**离散化** >* 扫描线一般运用在图形上面，它和它的字面意思十分相似，就是一条 ......
[数据结构]scanning line(扫描线)
# scanning line(扫描线) ## 1.1扫描线的思想以及在几何问题上的应用(eg1,3) ### [二维数点](http://oj.daimayuan.top/course/15/problem/686) 平面上有n个点(xi,yi)。 回答q个询问，每个询问给定一个矩形[X1,X2] ......
浅谈扫描线
# 扫描线 扫描线一般运用在图形上面，它和它的字面意思非常相似，就是拿一根线，在图形上面扫来扫去。我们一般用它来解决图形的面积，周长，二位数点等问题。 ## Atlantis 问题 在二维坐标系上，给出多个矩形的左下以及右上坐标，求出所有矩形构成的图形的面积。 我们当然知道，如果数据范围很小，我们可 ......