【模板】扫描线
2024年12月25日大约 5 分钟
离散化+权值线段树做法
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000; // 矩形的数量
int n;
int x[MAXN + 5], y[MAXN + 5], xx[MAXN + 5], yy[MAXN + 5];
// 离散化
vector<int> temp;
// 存每条竖线
struct Line
{
// (x,y)~(x,yy)
// typ == 1 矩形左边竖线
// typ == 2 矩形右边竖线
int x, y, yy, typ;
};
vector<Line> line; // 存每条线段
bool cmp(Line a, Line b)
{
return a.x < b.x;
}
// 线段树
int t[MAXN * 2 * 4 + 5]; //(要维护的权值数组长度为 MAXN*2)
int lazy[MAXN * 2 * 4 + 5];
// 重新计算当前的 t[now]
void up(int now, int l, int r)
{
if (lazy[now] > 0)
t[now] = temp[r + 1] - temp[l];
else if (l == r && lazy[now] == 0)
t[now] = 0;
else
t[now] = t[now * 2] + t[now * 2 + 1];
}
void update(int now, int l, int r, int x, int y, int z)
{
if (x <= l && r <= y)
{
lazy[now] += z;
up(now, l, r);
return;
}
int mid = (l + r) / 2;
if (x <= mid)
update(now * 2, l, mid, x, y, z);
if (y > mid)
update(now * 2 + 1, mid + 1, r, x, y, z);
up(now, l, r);
}
// 返回总长度和
int query()
{
return t[1];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
// 输入、离散化、构建线段
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> x[i] >> y[i] >> xx[i] >> yy[i];
temp.push_back(y[i]);
temp.push_back(yy[i]);
}
sort(temp.begin(), temp.end());
for (int i = 1; i <= n; i++)
{
// 范围 0~2n-1
y[i] = lower_bound(temp.begin(), temp.end(), y[i]) - temp.begin();
yy[i] = lower_bound(temp.begin(), temp.end(), yy[i]) - temp.begin();
// 把每条线段放入 line
line.push_back((Line){x[i], y[i], yy[i], +1});
line.push_back((Line){xx[i], y[i], yy[i], -1});
}
sort(line.begin(), line.end(), cmp);
// 从左往右扫描
long long ans = 0; // 记录总的面积并
int lastX = 0; // 记录上一条线段的 x 的位置
for (Line now : line)
{
ans += (long long)(now.x - lastX) * query();
lastX = now.x;
update(1, 0, 2 * n - 1, now.y, now.yy - 1, now.typ);
}
cout << ans << "\n";
return 0;
}动态开点权值线段树
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100000;
const int MAXTOT = MAXN * 120;
const int MAXXY = 1000000000;
int n;
int x[MAXN + 5], y[MAXN + 5], xx[MAXN + 5], yy[MAXN + 5];
struct Line
{
// (x,y)~(x,yy) typ:1 左边线，-1 右边线
int x, y, yy, typ;
};
vector<Line> line;
bool cmp(Line x, Line y)
{
return x.x < y.x;
}
// 动态开点权值线段树，区间修改，总和查询
int tot; // 当前用到的点数，编号从 1~tot
int lson[MAXTOT + 5], rson[MAXTOT + 5];
int t[MAXTOT + 5], lazy[MAXTOT + 5];
void up(int now, int l, int r)
{
if (lazy[now] > 0)
t[now] = r - l + 1;
else if (l == r && lazy[now] == 0)
t[now] = 0;
else
t[now] = t[lson[now]] + t[rson[now]];
}
void update(int now, int l, int r, int x, int y, int z)
{
if (x <= l && r <= y)
{
lazy[now] += z;
up(now, l, r);
return;
}
int mid = (l + r) / 2;
// 保证有左右子节点
if (lson[now] == 0)
lson[now] = ++tot;
if (rson[now] == 0)
rson[now] = ++tot;
// 分别尝试去两边修改
if (x <= mid)
update(lson[now], l, mid, x, y, z);
if (y > mid)
update(rson[now], mid + 1, r, x, y, z);
up(now, l, r);
}
int query()
{
return t[1];
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> x[i] >> y[i] >> xx[i] >> yy[i];
// 生成所有竖线/并排序
for (int i = 1; i <= n; i++)
{
line.push_back((Line){x[i], y[i], yy[i], 1});
line.push_back((Line){xx[i], y[i], yy[i], -1});
}
sort(line.begin(), line.end(), cmp);
// 动态开点线段树初始化
tot = 1;
// 扫描线
int ans = 0;
int lastX = 0; // 上一条线的 x 坐标
for (int i = 0; i < line.size(); i++)
{
ans += (line[i].x - lastX) * query();
lastX = line[i].x;
update(1, 0, MAXXY, line[i].y, line[i].yy - 1, line[i].typ);
}
cout << ans;
return 0;
}
```---
title: "P5490 【模板】扫描线"
---
## 离散化+权值线段树做法
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000; // 矩形的数量
int n;
int x[MAXN + 5], y[MAXN + 5], xx[MAXN + 5], yy[MAXN + 5];
// 离散化
vector<int> temp;
// 存每条竖线
struct Line
{
// (x,y)~(x,yy)
// typ == 1 矩形左边竖线
// typ == 2 矩形右边竖线
int x, y, yy, typ;
};
vector<Line> line; // 存每条线段
bool cmp(Line a, Line b)
{
return a.x < b.x;
}
// 线段树
int t[MAXN * 2 * 4 + 5]; //(要维护的权值数组长度为 MAXN*2)
int lazy[MAXN * 2 * 4 + 5];
// 重新计算当前的 t[now]
void up(int now, int l, int r)
{
if (lazy[now] > 0)
t[now] = temp[r + 1] - temp[l];
else if (l == r && lazy[now] == 0)
t[now] = 0;
else
t[now] = t[now * 2] + t[now * 2 + 1];
}
void update(int now, int l, int r, int x, int y, int z)
{
if (x <= l && r <= y)
{
lazy[now] += z;
up(now, l, r);
return;
}
int mid = (l + r) / 2;
if (x <= mid)
update(now * 2, l, mid, x, y, z);
if (y > mid)
update(now * 2 + 1, mid + 1, r, x, y, z);
up(now, l, r);
}
// 返回总长度和
int query()
{
return t[1];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
// 输入、离散化、构建线段
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> x[i] >> y[i] >> xx[i] >> yy[i];
temp.push_back(y[i]);
temp.push_back(yy[i]);
}
sort(temp.begin(), temp.end());
for (int i = 1; i <= n; i++)
{
// 范围 0~2n-1
y[i] = lower_bound(temp.begin(), temp.end(), y[i]) - temp.begin();
yy[i] = lower_bound(temp.begin(), temp.end(), yy[i]) - temp.begin();
// 把每条线段放入 line
line.push_back((Line){x[i], y[i], yy[i], +1});
line.push_back((Line){xx[i], y[i], yy[i], -1});
}
sort(line.begin(), line.end(), cmp);
// 从左往右扫描
long long ans = 0; // 记录总的面积并
int lastX = 0; // 记录上一条线段的 x 的位置
for (Line now : line)
{
ans += (long long)(now.x - lastX) * query();
lastX = now.x;
update(1, 0, 2 * n - 1, now.y, now.yy - 1, now.typ);
}
cout << ans << "\n";
return 0;
}动态开点权值线段树
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100000;
const int MAXTOT = MAXN * 120;
const int MAXXY = 1000000000;
int n;
int x[MAXN + 5], y[MAXN + 5], xx[MAXN + 5], yy[MAXN + 5];
struct Line
{
// (x,y)~(x,yy) typ:1 左边线，-1 右边线
int x, y, yy, typ;
};
vector<Line> line;
bool cmp(Line x, Line y)
{
return x.x < y.x;
}
// 动态开点权值线段树，区间修改，总和查询
int tot; // 当前用到的点数，编号从 1~tot
int lson[MAXTOT + 5], rson[MAXTOT + 5];
int t[MAXTOT + 5], lazy[MAXTOT + 5];
void up(int now, int l, int r)
{
if (lazy[now] > 0)
t[now] = r - l + 1;
else if (l == r && lazy[now] == 0)
t[now] = 0;
else
t[now] = t[lson[now]] + t[rson[now]];
}
void update(int now, int l, int r, int x, int y, int z)
{
if (x <= l && r <= y)
{
lazy[now] += z;
up(now, l, r);
return;
}
int mid = (l + r) / 2;
// 保证有左右子节点
if (lson[now] == 0)
lson[now] = ++tot;
if (rson[now] == 0)
rson[now] = ++tot;
// 分别尝试去两边修改
if (x <= mid)
update(lson[now], l, mid, x, y, z);
if (y > mid)
update(rson[now], mid + 1, r, x, y, z);
up(now, l, r);
}
int query()
{
return t[1];
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> x[i] >> y[i] >> xx[i] >> yy[i];
// 生成所有竖线/并排序
for (int i = 1; i <= n; i++)
{
line.push_back((Line){x[i], y[i], yy[i], 1});
line.push_back((Line){xx[i], y[i], yy[i], -1});
}
sort(line.begin(), line.end(), cmp);
// 动态开点线段树初始化
tot = 1;
// 扫描线
int ans = 0;
int lastX = 0; // 上一条线的 x 坐标
for (int i = 0; i < line.size(); i++)
{
ans += (line[i].x - lastX) * query();
lastX = line[i].x;
update(1, 0, MAXXY, line[i].y, line[i].yy - 1, line[i].typ);
}
cout << ans;
return 0;
}