信竞学习笔记：扫描线

Tiger

发表于 2026-07-22

更新于 2026-07-22

2 2.2~2.8 分钟 990

注：这是本人的课堂笔记。

扫描线是一种应用于图形的算法，主要用于解决图形面积、周长等问题。

扫描线

例题：P5490

本题使用线段树这种数据结构对扫描线进行维护，其核心是有一根平行于坐标轴的线在坐标平面内往一个方向扫描。下面以从下往上扫描为例。

首先，对所有点的纵坐标记录下来进行排序，将所有 $n$ 个横坐标投射到一个坐标轴上，产生 $n-1$ 条线段。使用线段树维护这 $n-1$ 条线段。

假设有一条直线从下往上扫过整个图形，会在某些与原图形重合的线段的位置进行停留。为实现这一目的，我们要记录直线是进入还是离开图形，通常用 $1$ 代表进入， $-1$ 代表离开，这样可以用每条线段的权值快速计算。

在进入或离开某个图形的时候，我们要记录哪个线段变得有效或无效。之后计算出扫过图形的面积：计算出在 $y$ 轴上移动的距离，乘上 $x$ 轴上的宽，也就是权值大于等于 $1$ 的线段的长度的和 $\sum\limits_{a_i \geq 1} len_i$ 。直至扫过整个图形。

代码如下：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2e6 + 100;
int n, cnt, num;
ll px[N<<1], t[N<<2], tag[N<<2], sum[N<<2];
ll ans;
struct st {
	ll x1, x2, y, v;
	bool operator<(const st &other) const {
		return y < other.y;
	}
} lin[N<<1];

void build(int u, int l, int r) {
	if (l == r) t[u] = px[l+1] - px[l];
	else {
		int mid = l + r >> 1;
		build(u<<1, l, mid);
		build(u<<1|1, mid+1, r);
		t[u] = t[u<<1] + t[u<<1|1];
	}
}

void pushup(int u) {
	if (tag[u] > 0) sum[u] = t[u];
	else sum[u] = sum[u<<1] + sum[u<<1|1];
}

void update(int u, int l, int r, int L, int R, ll v) {
	if (L <= l && r <= R) {
		tag[u] += v;
		pushup(u);
		return;
	}
	int mid = l + r >> 1;
	if (L <= mid) update(u<<1, l, mid, L, R, v);
	if (R > mid) update(u<<1|1, mid+1, r, L, R, v);
	pushup(u);
}

int main() {
	
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	
	cin >> n;
	
	for (int i=1; i<=n; i++) {
		ll X1, X2, Y1, Y2;
		cin >> X1 >> Y1 >> X2 >> Y2;
		lin[++cnt] = {X1, X2, Y1, 1};
		px[cnt] = X1;
		lin[++cnt] = {X1, X2, Y2, -1};
		px[cnt] = X2;
	}
	
	sort(lin+1, lin+cnt+1);
	sort(px+1, px+cnt+1);
	num = unique(px+1, px+cnt+1) - px - 1;
	
	build(1, 1, num-1);
	
	for (int i=1; i<=cnt; i++) {
		ans += sum[1] * (lin[i].y - lin[i-1].y);
		int l = lower_bound(px+1, px+num+1, lin[i].x1) - px;
		int r = lower_bound(px+1, px+num+1, lin[i].x2) - px;
		update(1, 1, num-1, l, r-1, lin[i].v);
	}
	
	cout << ans;
	
	return 0;
}

离线二维数点

例题：P10814

对于每个询问，求 $[l,r]$ 中小于等于 $x$ 的元素个数，即求 $[1,l-1]$ 中小于等于 $x$ 的元素个数与 $[1,r]$ 中小于等于 $x$ 的元素个数之差。于是，我们只需要关心前缀中小于等于 $x$ 的元素的个数。

运用扫描线的思想，从小往大扫。将所有询问存储下（询问离线），用树状数组维护权值，扫描一遍即可在约 $O(n \log n)$ 的时间内扫描完成得到答案。总时间复杂度 $O(n \log n)$ 。

代码如下：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2e6 + 100;
int n, m;
ll a[N], t[N], ans[N];
struct node {
	ll x, id, v;
};
vector<node> g[N];

ll lowbit(ll x) {
	return x & (-x);
}

void add(ll x, ll y) {
	for (ll i=x; i<=2e6; i+=lowbit(i)) t[i] += y;
}

ll sum(int x) {
	ll res = 0;
	for (ll i=x; i; i-=lowbit(i)) res += t[i];
	return res;
}

int main() {
	
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	
	cin >> n >> m;
	
	for (int i=1; i<=n; i++) cin >> a[i];
	
	for (int i=1; i<=m; i++) {
		ll l, r, x;
		cin >> l >> r >> x;
		g[l-1].push_back({x, i, -1});
		g[r].push_back({x, i, 1}); 
	}
	
	for (int i=1; i<=n; i++) {
		add(a[i], 1);
		for (const node &p : g[i]) {
			ans[p.id] += sum(p.x) * p.v;
		}
	}
	
	for (int i=1; i<=m; i++) {
		cout << ans[i] << "\n";
	}
	
	return 0;
}