深入扫描线
KazamaRuri
·
·
算法·理论
本文默认为右端点扩展的扫描线。
常规
函数复合及矩阵修改。
排队
f_i(x)=x+[x\in[l_i,r_i]]，f_r(f_{r-1}\dots f_l(0)) ?
函数复合模板题吧，lxl 和校内都讲过。
扫描线移动时，在数据结构里把值域在范围内的元素 +1 就好啦。
询问就维护元素在数据结构的指针。
treap 有交合并可 O(n\log^2 n)，树状数组二分可 O(n\log n)。
A simple rmq problem
区间只出现一次的数的最大值。
对序列建系，把区间视作二维的点 (l,r)。
对于 a_i，其影响的点满足 l \in [pre+1,i]\ \vee\ r \in [i,nxt-1]。
矩阵 max 单点询问，树套树 O(n \log^2 n)。
TEST_152
给定操作序列 (l_i,r_i,v_i)，意为区间推平 c_{l:r} \leftarrow v。
问顺序执行 [L,R] 的操作后的序列之和，序列初值为 0。
询问难搞，修改可以珂朵莉树，因为只有推平且推平次数是 O(n) 的，所以时间摊下来肯定是对的，不怕被卡。
按操作序列扫描，维护颜色序列维。
操作变成区间推平所造成的若干次单点修改，以及若干次的区间查询。BIT + ODT 能 O(n\log n)。
历史版本和
问 \sum\sum f(l,r)。
考虑离线扫描线维护。
对于某个 l，当扫描线右端点扫到 r。
我们需要把 r 的贡献加上使得 v_l 的值 f(l,r-1) \rightarrow f(l,r)。
发现对于每个询问，固定 l，其贡献为 \sum_r f(l,r)。
这正是 v_l 在 (r'=l) \sim r 时刻每一刻值之和，即历史版本和。
但是肯定不能暴力求和，考虑在数据结构上打贡献标记即可。
标记设计可能有很多（包括贡献标记和修改标记），但都是为了维护节点的历史版本和服务。
Prof. Pang's sequence
f(l,r)=[区间颜色数为奇数]
扫描线移动到 i，会导致 [pre+1,i] 反转。
历史版本和一般默认使用线段树。
设计标记 t_{0/1},tg_{0/1}，分别表示奇偶点数量（f 值为 0/1 的数量）和贡献次数的懒标记。
反转的影响为交换奇偶标记，由于是区间反转所以还要多一个 rev 的懒标记。
扫描线移动时把根节点的 tg_1 \leftarrow tg_1 + 1，表示此刻的奇点贡献次数增加。
Good Subsegments
f(l,r)=[区间的数排序后值域连续]
转化得到
f(l,r)=[\max-\min-(r-l)=0]
考虑直接维护 \max-\min-r+l 的值，因为这个值总是非负（排列，所以极差总大于长度）。
那么每次贡献就是值 =0 的点数量。
因为扫描线在 r 时，f(r,r)=0，所以根节点最小值总是为 0，答案就是最小值的数量，这一步是巧妙的。
线段树维护 \min,cnt 表示区间最小值及其数量。
注意，为了保证是最小值的数量才能贡献，贡献标记下放时要保证 \min_x = \min_{fa}。
如何把 min/max 的变化也转成加减的形式呢？
这是经典 trick，单调栈维护，每轮被弹出栈的所构成的区间 min/max 变小/大，等价于区间加减，容易维护。
时间复杂度 $O(n\log n)$。
### 比赛
$$
f(l,r)=\max a_i \cdot \max b_i
$$
$\max$ 的维护同上题。标记大概要维护区间长度，$\max a$ 的和，$\max b$ 的和，$\max a \cdot \max b$ 的历史版本和，以及普遍的贡献标记和加法懒标记。
由于标记非常多，用矩阵来转移会清晰很多。但是，你知道的呀，三次方的常数，不循环展开大概率 T 的。
时间复杂度是大常数 $O(n\log n)$。
## 隐式时间维
这类问题通常表现为修改和询问一起复杂一个简单。
而应对手段是无中生有 —— 拓展时间维度，转为在二维平面上的扫描线问题。
### 无题
区间加，单点询问历史最值。
直接做不太可做，麻烦。
那么，如果不顺着操作时间做呢？
把时间视作维度，按序列进行扫描线：
欸，现在修改变成了单点加减，询问变成了前缀最大值。差分成后缀加减，区间最值，这是 ez 的。
线段树 $O(n\log n)$。
### フードコート（饮食区）
维护一个序列，序列中每个元素是一个队列。
入队操作，往队列 $[l,r]$ 里放进 $k$ 个 $c$。
出队操作，让 $[l,r]$ 的队列从队首出 $k$ 个数，不足 $k$ 则只清空。
询问操作，问当前时刻队列 $a$ 里第 $b$ 个数是多少，没有则为 0。
因为我懒得写了，直接搬[自己写的题解](https://www.luogu.com.cn/article/zeouy6ck)吧:
发现修改非常难办，考虑把时间轴竖过来，按序列维扫描线，转化成单点修改。
思考：删除元素的时候会“顶格”，即对 $0$ 取 $\max$。如果不会顶格，那我们可以把所有加操作提前，把减操作后置，然后二分到最靠前的加操作使得 $\sum add \ge \sum del + b$，其中 $b$ 为询问中的。发现如果我们找到当前询问的时间戳 $t$ 之前的最后一次队列为 $0$ 的时刻，那么只考虑这个时刻后面的加减操作，就可以套用上述算法。
现在问题在于，如何求出“时间戳 $t$ 之前的最后一次队列为 $0$ 的时刻”。序列被清空的充要条件是经过一段操作后，变化量 $\le 0$。这就说明时间戳上每一个前缀最小值的位置都对应了一次清空。
维护前缀最小值位置不好做，差分一下转变成整体最小值位置，这是可以维护区间最小值 + 线段树二分解决的。同时，单点修改变成一段后缀的修改，这是 ez 的。
顺带一提，如果前缀最小值 $>0$，即没有被清空过，要把上一次清空的时刻视作所有操作开始前（$0$ 时刻）。
至此，问题解决完了。实现上，按时间轴维护两颗线段树，一颗处理所有操作，即加减操作的贡献，维护最小值以查找最后一次序列被清空的位置；另一颗只维护加操作，维护最大值以处理无顶格情况下对形如 $\ge x$ 的最后一个位置的询问。为什么不维护减法的呢？因为 $\sum add - \sum del = \sum total$。
时间复杂度 $O(n \log n)$。