扫描线

扫描线的精髓是通过离线、引入时间维，把静态询问降低一维、变成动态问题。

一般是先把若干询问通过可减性变成前缀询问，再离线、从左到右排序，从左到右一个一个地一边加入元素，一边回答询问。

以下是例题 + 一句话题解。（虽然可能不是真的一句话）

平面最值

二维平面上 \(n(\le10^5)\) 个点，每个点有权值 \((\le10^9)\)，\(m(\le10^5)\) 次询问 \((a,b,c)\)，求满足 \(x_i\le a\) 且 \(y_i\in[b..c]\) 的最大点权。

离线、排序、离散化，需要支持加入点、求区间 \(\max\)。

二维数点

\(n(\le10^5)\) 个数的正整数序列，\(m(\le10^5)\) 次询问下标范围 \([l..r]\) 内元素值属于 \([x..y]\) 的个数。

经典题，把询问拆成两个前缀、离线，需要支持加入点、前缀求和。

HH 的项链

\(n(\le10^6)\) 个数的正整数序列 \(a_i(\le10^6)\)，\(m(\le10^6)\) 次询问区间 \([l..r]\) 内不同的数的个数。

记录每个数上一个与它权值相同的数的位置 \(las_i\)，问题转化为求 \([l,r]\) 内有多少 \(las_i<l\)；拆分、离线、排序，需要支持加入一个数、前缀求和。

连通块计数

\(n(\le10^6)\) 个点的树，点编号 \(1\sim n\)、边编号 \(1\sim n-1\)，\(m(\le10^6)\) 次询问 \(l,r\)，若只考虑编号在 \(l..r\) 中的点和边，共多少个连通块？

每加一条边，连通块数就 \(-1\)，故考虑有多少条边 \((u,v,id)\) 有效，即 \(u,v,id\) 均属于 \([l..r]\)；再取个 \(\max\)、\(\min\)，变成要求两个参数属于 \([l..r]\)，扫一遍即可。

矩形周长、面积并

二维平面上 \(n(\le10^5)\) 个边平行于坐标轴的矩形，求覆盖的总面积、总周长，坐标绝对值 \(\le10^9\)。

离散化坐标，直接扫描线，区间加、全局查一共多少位置 \(>0\)，所以线段树每个节点多记一个数表示区间总变化量 \(c\)（标记永久化），若 \(c>0\) 节点值为区间长；若 \(c=0\) 节点值为儿子值之和。仔细理解发现一定是对的。

注意一个很坑的地方：若两个矩形的边部分重合，要考虑重合部分周长是否算进去。