扫描线
引入
扫描线一般运用在图形上面，它和它的字面意思十分相似，就是一条线在整个图上扫来扫去，它一般被用来解决图形面积，周长，以及二维数点等问题。
Atlantis 问题
题意
在二维坐标系上，给出多个矩形的左下以及右上坐标，求出所有矩形构成的图形的面积。
解法
根据图片可知总面积可以直接暴力即可求出面积，如果数据大了怎么办？这时就需要讲到 扫描线 算法。
过程
现在假设我们有一根线，从下往上开始扫描：
- 如图所示，我们可以把整个矩形分成如图各个颜色不同的小矩形，那么这个小矩形的高就是我们扫过的距离，那么剩下了一个变量，那就是矩形的长一直在变化。
- 我们的线段树就是为了维护矩形的长，我们给每一个矩形的上下边进行标记，下面的边标记为 1，上面的边标记为 -1，每遇到一个矩形时，我们知道了标记为 1 的边，我们就加进来这一条矩形的长，等到扫描到 -1 时，证明这一条边需要删除，就删去，利用 1 和 -1 可以轻松的到这种状态。
- 还要注意这里的线段树指的并不是线段的一个端点，而指的是一个区间，所以我们要计算的是
和 。 - 需要 离散化。
实现
代码实现
#include <algorithm>
#include <cstdio>
#include <cstring>
#define maxn 300
using namespace std;
int lazy[maxn << 3]; // 标记了这条线段出现的次数
double s[maxn << 3];
struct node1 {
double l, r;
double sum;
} cl[maxn << 3]; // 线段树
struct node2 {
double x, y1, y2;
int flag;
} p[maxn << 3]; // 坐标
// 定义sort比较
bool cmp(node2 a, node2 b) { return a.x < b.x; }
// 上传
void pushup(int rt) {
if (lazy[rt] > 0)
cl[rt].sum = cl[rt].r - cl[rt].l;
else
cl[rt].sum = cl[rt * 2].sum + cl[rt * 2 + 1].sum;
}
// 建树
void build(int rt, int l, int r) {
if (r - l > 1) {
cl[rt].l = s[l];
cl[rt].r = s[r];
build(rt * 2, l, (l + r) / 2);
build(rt * 2 + 1, (l + r) / 2, r);
pushup(rt);
} else {
cl[rt].l = s[l];
cl[rt].r = s[r];
cl[rt].sum = 0;
}
return;
}
// 更新
void update(int rt, double y1, double y2, int flag) {
if (cl[rt].l == y1 && cl[rt].r == y2) {
lazy[rt] += flag;
pushup(rt);
return;
} else {
if (cl[rt * 2].r > y1) update(rt * 2, y1, min(cl[rt * 2].r, y2), flag);
if (cl[rt * 2 + 1].l < y2)
update(rt * 2 + 1, max(cl[rt * 2 + 1].l, y1), y2, flag);
pushup(rt);
}
}
int main() {
int temp = 1, n;
double x1, y1, x2, y2, ans;
while (scanf("%d", &n) && n) {
ans = 0;
for (int i = 0; i < n; i++) {
scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
p[i].x = x1;
p[i].y1 = y1;
p[i].y2 = y2;
p[i].flag = 1;
p[i + n].x = x2;
p[i + n].y1 = y1;
p[i + n].y2 = y2;
p[i + n].flag = -1;
s[i + 1] = y1;
s[i + n + 1] = y2;
}
sort(s + 1, s + (2 * n + 1)); // 离散化
sort(p, p + 2 * n, cmp); // 把矩形的边的横坐标从小到大排序
build(1, 1, 2 * n); // 建树
memset(lazy, 0, sizeof(lazy));
update(1, p[0].y1, p[0].y2, p[0].flag);
for (int i = 1; i < 2 * n; i++) {
ans += (p[i].x - p[i - 1].x) * cl[1].sum;
update(1, p[i].y1, p[i].y2, p[i].flag);
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n", temp++, ans);
}
return 0;
}
练习
B 维正交范围
B 维正交范围指在一个 B 维直角坐标系下，第
一般来说，一维正交范围简称区间，二维正交范围简称矩形，三维正交范围简称立方体（我们常说的二维数点就是二维正交范围）。
对于一个静态的二维问题，我们可以使用扫描线扫一维，数据结构维护另一维。 在扫描线从左到右扫的过程中，会在数据结构维护的那一维上产生一些修改与查询。 如果查询的信息可差分的话直接使用差分，否则需要使用分治。差分一般用树状数组和线段树维护，但因为树状数组好写而且常数小，所以大部分人会选择用树状数组来维护。分治一般是 CDQ 分治（但是这里不涉及分治）。
另一种比较容易理解的看待问题的角度是站在序列角度，而不站在二维平面角度。如果我们这样看待问题，则扫描线实际上是枚举了右端点
复杂度一般为
二维数点
给一个长为
这个问题就叫做二维数点。我们可以发现等价于我们要查询一个二维平面上矩形内的点的数量和。这里讲一下这个问题最简单的处理方法，扫描线 + 树状数组。
很显然，这个问题是一个静态的二维问题，我们通过扫描线可以将静态的二维问题转换为动态的一维问题。维护动态的一维问题就使用数据结构维护序列，这里可以使用树状数组。
先将所有的询问离散化，用树状数组维护权值，对于每次询问的
例题
洛谷 P2163[SHOI2007] 园丁的烦恼
首先离散化。设一个左下角为
代码
#include <bits/stdc++.h>
int n, m;
int x[500010], y[500010], ans[500010];
int ax[1500010], ay[1500010], tx, ty; // 离散化
struct query {
int a, b, c, d;
} q[500010]; // 保存查询操作方便离散化
struct ope {
int type, x, y, id;
inline ope(int type = 0, int x = 0, int y = 0, int id = 0) {
this->type = type, this->x = x, this->y = y, this->id = id;
}
inline bool operator<(const ope& rhs) const {
if (x == rhs.x) return type < rhs.type;
return x < rhs.x;
}
};
ope op[2500010];
int tot; // 操作总数
int sum[1500010]; // 树状数组
int lowbit(int x) { return x & (-x); }
void add(int x, int k) {
while (x <= 1500000) {
sum[x] = sum[x] + k;
x = x + lowbit(x);
}
}
int getsum(int x) {
int ret = 0;
while (x > 0) {
ret = ret + sum[x];
x = x - lowbit(x);
}
return ret;
}
int main() {
scanf("%d%d", &n, &m), tx = n, ty = n;
for (int i = 1; i <= n; i++)
scanf("%d%d", &x[i], &y[i]), ax[i] = x[i], ay[i] = y[i];
for (int i = 1, l, r; i <= m; i++) {
scanf("%d%d%d%d", &q[i].a, &q[i].b, &q[i].c, &q[i].d);
ax[++tx] = q[i].a, ay[++ty] = q[i].b, ax[++tx] = q[i].c, ay[++ty] = q[i].d;
}
std::sort(ax + 1, ax + tx + 1), std::sort(ay + 1, ay + ty + 1);
tx = std::unique(ax + 1, ax + tx + 1) - ax - 1;
ty = std::unique(ay + 1, ay + ty + 1) - ay - 1;
for (int i = 1; i <= n; i++) {
x[i] = std::lower_bound(ax + 1, ax + tx + 1, x[i]) - ax;
y[i] = std::lower_bound(ay + 1, ay + ty + 1, y[i]) - ay;
op[++tot] = ope(0, x[i], y[i], i); // 加点操作
}
for (int i = 1; i <= m; i++) {
q[i].a = std::lower_bound(ax + 1, ax + tx + 1, q[i].a) - ax;
q[i].b = std::lower_bound(ay + 1, ay + ty + 1, q[i].b) - ay;
q[i].c = std::lower_bound(ax + 1, ax + tx + 1, q[i].c) - ax;
q[i].d = std::lower_bound(ay + 1, ay + ty + 1, q[i].d) - ay;
op[++tot] = ope(1, q[i].c, q[i].d, i); // 将查询差分
op[++tot] = ope(1, q[i].a - 1, q[i].b - 1, i);
op[++tot] = ope(2, q[i].a - 1, q[i].d, i);
op[++tot] = ope(2, q[i].c, q[i].b - 1, i);
}
std::sort(op + 1, op + tot + 1); // 将操作按横坐标排序，且优先执行加点操作
for (int i = 1; i <= tot; i++) {
if (op[i].type == 0)
add(op[i].y, 1);
else if (op[i].type == 1)
ans[op[i].id] += getsum(op[i].y);
else
ans[op[i].id] -= getsum(op[i].y);
}
for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
return 0;
}
洛谷 P1908 逆序对
没错，逆序对也可以用扫描线的思维来做。考虑将求逆序对的个数转化为从后向前枚举每个位置
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node {
ll data;
ll num;
} f[500010];
ll n, ans, a[500010];
bool cmp(node a, node b) {
if (a.data == b.data) {
return a.num < b.num;
}
return a.data < b.data;
}
ll sum[500010];
int lowbit(int x) { return x & (-x); }
void add(int x, int k) {
while (x <= n) {
sum[x] = sum[x] + k;
x = x + lowbit(x);
}
}
int getsum(int x) {
int ret = 0;
while (x > 0) {
ret = ret + sum[x];
x = x - lowbit(x);
}
return ret;
}
int main() {
cin >> n;
for (ll i = 1; i <= n; i++) {
cin >> f[i].data;
f[i].num = i;
}
sort(f + 1, f + 1 + n, cmp);
for (int i = 1; i <= n; i++) {
a[f[i].num] = i;
}
for (ll i = n; i > 0; i--) {
ans += getsum(a[i]);
add(a[i], 1);
}
cout << ans;
return 0;
}
洛谷 P1972 [SDOI2009] HH 的项链
简要题意：给定一个序列，多次询问区间
这类问题我们可以考虑推导性质，之后使用扫描线枚举所有右端点，数据结构维护每个左端点的答案的方法来实现，我们也可以将问题转换到二维平面上，变为一个矩形查询信息的问题。
在本题中，我们设序列中
现在问题即为：给定一个序列
我们可以把
注意到这个询问是可差分的，我们可以将询问差分为左下角为
单次操作复杂度
代码
#include <bits/stdc++.h>
int n, m, a[1000010], ans[1000010];
int pre[1000010], lst[1000010]; // 处理 pre
struct ope {
int type, x, y, id;
inline ope(int type = 0, int x = 0, int y = 0, int id = 0) {
this->type = type, this->x = x, this->y = y, this->id = id;
}
inline bool operator<(const ope& rhs) const {
if (x == rhs.x) return type < rhs.type;
return x < rhs.x;
}
};
ope op[2500010];
int tot; // 操作总数
int sum[1000010]; // 树状数组
int lowbit(int x) { return x & (-x); }
void add(int x, int k) {
x++; // 位置 0 也要进行修改，所以树状数组下标均加 1
while (x <= n) {
sum[x] = sum[x] + k;
x = x + lowbit(x);
}
}
int getsum(int x) {
x++;
int ret = 0;
while (x > 0) {
ret = ret + sum[x];
x = x - lowbit(x);
}
return ret;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
pre[i] = lst[a[i]], lst[a[i]] = i; // 处理 pre
op[++tot] = (ope){0, i, pre[i], i}; // 加点操作
}
scanf("%d", &m);
for (int i = 1, l, r; i <= m; i++) {
scanf("%d%d", &l, &r);
op[++tot] = (ope){1, r, l - 1, i}; // 将查询差分
op[++tot] = (ope){2, l - 1, l - 1, i};
}
std::sort(op + 1, op + tot + 1); // 将操作按横坐标排序，且优先执行加点操作
for (int i = 1; i <= tot; i++) {
if (op[i].type == 0)
add(op[i].y, 1);
else if (op[i].type == 1)
ans[op[i].id] += getsum(op[i].y);
else
ans[op[i].id] -= getsum(op[i].y);
}
for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
return 0;
}
例题
-
洛谷 P8593「KDOI-02」一个弹的投 逆序对的应用。
-
AcWing 4709. 三元组 上题的弱化版，同样为逆序对的应用。
-
洛谷 P8773[蓝桥杯 2022 省 A] 选数异或 HH 的项链魔改版。
-
洛谷 P8844[传智杯 #4 初赛] 小卡与落叶 树上问题转序列问题然后进行二维数点。
总而言之，二维数点的主要思路就是数据结构维护一维，然后枚举另一维。
参考资料
创建日期: July 11, 2018