Auguryの扫描线分享
扫描线是啥
有时候答案是不好计算的，但是答案可以拆分成多个段分别计算，且段与段之间可以快速转换，我们就可以用扫描线解决。
或者说，一个二维问题，我们可以用扫描线变成一维。
前置芝士
- 线段树、值域线段树、树状数组（胡扬好闪，拜谢胡扬）
- 离散化
现在我们有一堆数，你要处理与这堆数所在的值域区间相关的问题。
但是直接暴力遍历肯定太慢了，我们考虑把这些数排个序，去个重，标个号，然后问题就方便处理了。
具体地，我们记 \(a_i\) 为原序列的第 \(i\) 个元素，\(mp_i\) 表示排名为 \(i\) 的数的值，\(rk_i\) 为第 \(i\) 个数的排名。
然后，我们把序列扔进一个vector里面，然后排序，去重，求出 \(mp\)，然后在 \(mp\) 上二分即可求出 \(rk\)。
代码：void lsh(){ for(int i=1;i<=n;i++)mp.push_back(a[i]); sort(mp.begin(),mp.end());//排序 mp.erase(unique(mp.begin(),mp.end()),mp.end());//去重 for(int i=1;i<=n;i++)rk[i]=lower_bound(mp.begin(),mp.end(),a[i])-mp.begin();//转换 }
P1908 逆序对
热身题。
题意
求序列的逆序对数。
做法
对于每个点，我们求出他前面的、比它大的元素的个数，加起来就行了。
这个东西可以简单的用值域线段树维护（单点加、区间求和）或者离散化后用普通线段树维护。
P5490 【模板】扫描线
题意
求 \(n\) 个四边平行于坐标轴的矩形的面积并。
\(1 \le n \le {10}^5\)，\(0 \le x_1 < x_2 \le {10}^9\)，\(0 \le y_1 < y_2 \le {10}^9\)。
思路
先考虑一个弱化版，如果这些矩形的左右端点都分别相同，如下图：
这种情况我们就求出这些矩形的高度的并和宽度就行了。
但是高度的并和怎么求呢？
这就是一个值域线段树的区间赋值、区间求和。
然后我们考虑矩形变多的情况，如下图：
首先，我们考虑把这个东西分段，变成上面那样简单的形式。
显然，我们要以矩形的左右边界为分界点。
然后这张图就变成了这样：
那么，对于每一段，我们做一遍上面那个东西（？）
这样肯定会爆。
我们考虑把上一段重复贡献利用起来。
假如这一段我们到了一个矩形的右端点，那么显然我们要把这个矩形的贡献撤销掉。
但是如果是上面那个做法，我们啪一个区间赋 \(0\)，这一块就全没了！这样显然是错的！
所以我们考虑换成区间加，但是这样不好算 \(\ge 1\) 的值的个数。
所以我们正难则反，求 \(0\) 的个数。
我们在线段树的节点维护区间最小值和最小值的个数。显然全局的最小值个数就是 \(0\) 的个数了。
然后我们就能做单个段了。段与段之间直接加起来就行了。
然后这题就做完了。
P3660 [USACO17FEB] Why Did the Cow Cross the Road III G
题意
给定长度为 \(2N\) 的序列，\(1\sim N\) 各出现过 \(2\) 次，\(i\) 第一次出现位置记为 \(a_i\)，第二次记为 \(b_i\)，求满足 \(ai<aj<bi<bj\) 的对数。
做法
乍一看，这题要求交叉的区间数量
然后我们转念一想，这不就是要求按 \(b\) 排序后的 \(a\) 的逆序对数量吗。
直接类比上一题即可。
P3605 [USACO17JAN] Promotion Counting P
题面
奶牛们又一次试图创建一家创业公司，还是没有从过去的经验中吸取教训——牛是可怕的管理者！
为了方便，把奶牛从 \(1\sim n\) 编号，把公司组织成一棵树，1 号奶牛作为总裁（这棵树的根节点）。除了总裁以外的每头奶牛都有一个单独的上司（它在树上的 “双亲结点”）。
所有的第 \(i\) 头牛都有一个不同的能力指数 \(p_i\)，描述了她对其工作的擅长程度。如果奶牛 \(i\) 是奶牛 \(j\) 的祖先节点，那么我们我们把奶牛 \(j\) 叫做 \(i\) 的下属。
不幸地是，奶牛们发现经常发生一个上司比她的一些下属能力低的情况，在这种情况下，上司应当考虑晋升她的一些下属。你的任务是帮助奶牛弄清楚这是什么时候发生的。简而言之，对于公司的中的每一头奶牛 \(i\)，请计算其下属 \(j\) 的数量满足 \(p_j > p_i\)。
简要题意
求树上的逆序对数。
做法
我们已经会做序列的逆序对数了，对吧
我们考虑把这个东西放到树上。
具体地，我们考虑这棵树的 dfs 序。
我们记 \(dfn_i\) 为第 \(i\) 个点在 dfs 序上的位置，\(hi_i\) 为这个点的子树中 \(dfn\) 的最大值。
那么，\(dfn\) 在 \([dfn_i,hi_i]\) 中的点，都在这棵树的子树内。
所以，我们就要查询 \(dfn\) 在某个区间内，值在某个区间内的值的个数。
我们考虑把值放在 dfs 序上，就变成了求区间内值在某个区间的数的个数。
那这个东西怎么做呢？
我们已经会求前缀的答案了，那我直接把两个前缀的答案作差就行了呗。
所以把询问挂到区间上，从左往右扫，顺便维护一个值域线段树即可。
然后这题就做完了。
P1972 [SDOI2009] HH的项链
zjj 闪亮登场！
题面
HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。
有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答…… 因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。
题意
给你一个序列，多次询问区间颜色种类数。
做法
我们考虑什么数会产生贡献。
容易发现，只有在这个区间内出现过，且上一次出现位置不在这个区间内的数才会产生贡献。
也就是说，要求位置在 \([l,r]\) 中，上一次出现位置在 \([1,l-1]\) 的数的个数。
显然这是一个矩阵求和问题。
所以我们把询问挂在右端点上，开一个线段树，从左往右扫，每个下标维护上一次出现在这个位置的数的个数。
然后对于每个区间，我们查询 \([0,l-1]\) 的区间和，就是答案。
UVA1608 不无聊的序列 Non-boring sequences
题意
如果一个序列的任意连续子序列都至少有一个元素唯一，则称这个序列“不无聊”，否则称这个序列“无聊”。给定T个序列，求是否“无聊”。
做法
还是考虑每个数的贡献。我们记 \(pre_i\) 为 \(i\) 位置数上一次出现的位置，\(suf_i\) 为下一次出现的位置。
那么，\(i\) 这个数只会对左端点在 \([pre_i+1,i]\)，右端点在 \([i,suf_i-1]\) 的区间贡献。
我们以 \(l\) 为横坐标，\(r\) 为右坐标，将每个数的贡献视为矩形，那么每个点都代表一个区间，合法区间的数量就是这些矩形的并的面积。
那么我们只需要判断这些矩形的面积的并是不是 \(\frac{n(n+1)}{2}\) 即可。
P1502 窗口的星星
题面
晚上，小卡从阳台望出去，“哇~~~~好多星星啊”，但他还没给其他房间设一个窗户。
天真的小卡总是希望能够在晚上能看到最多最亮的星星，但是窗子的大小是固定的，边也必须和地面平行。
这时小卡使用了超能力（透视术）知道了墙后面每个星星的位置和亮度，但是小卡发动超能力后就很疲劳，只好拜托你告诉他最多能够有总和多亮的星星能出现在窗口上。
题意
求矩形和的最大值。
做法
先来想想序列怎么做，也就是单点加、区间和最大值怎么做。
这肯定是不好做的，但是我们会做区间加全局最大值。
所以我们把每个单点加变成区间加，然后就可以做了。
然后我们考虑这道题。不就变成了矩阵加、单点最大值吗？
直接扫描线维护即可。