首页 > 其他分享 >「学习笔记」扫描线

「学习笔记」扫描线

时间：2023-08-06 15:11:06浏览次数：50  
标签：ch return int 线段 笔记 学习 read 扫描线 line

什么是扫描线？顾名思义，一根用来扫描的线

扫描线就是一条线在整个图上扫来扫去，它一般被用来解决图形面积，周长，以及二维数点等问题。

下面我们用例题来引入。

P5490 【模板】扫描线 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

我们对于这种题有三种做法

  1. 暴力的进行覆盖扫描

  2. 容斥

  3. 线段树

第一种做法，你会 T 或者 MLE 或者两者兼得；第二种做法，你的脑子会 RE 如果真的是数学神仙就忽略这句话；第三种做法，就是我们今天的主角——扫描线。

过程

扫描线的大体思路是这样的。

这个动图来自 \(\texttt{OI-Wiki}\)。

这个图很生动形象，它所展示的就是扫描线的过程，现在我们来讲一下该如何实现它。

实现

对于扫描线，我们用线段树来实现它，每个节点维护的都是线段 真·线段树，在线段树中，我们要维护这一条线段的左右端点（即起始和终止位置），以及这个线段的高度；线段树中记录的是这个节点对应的线段的左端点在数组中的标号、右端点在数组中的编号，以及覆盖标记和覆盖长度。

struct node {
    int val;
    ll L, R, H;
    // val 该线段是否存在
    // L, R 左右端点
    // H 高度
} line[N << 1];

struct seg {
    int L, R, tag;
    ll sum;
    // L, R 左右短点
    // sum 被覆盖的长度
    // tag 是否被完全覆盖
} t[N << 3];

我们在输入的时候要记录一个图形的开始位置和结束位置。

for (int i = 1; i <= n; ++ i) {
    int x_1 = read<ll>(), y_1 = read<ll>(), x_2 = read<ll>(), y_2 = read<ll>();
    line[i] = node{1, x_1, x_2, y_1};
    line[i + n] = node{-1, x_1, x_2, y_2};
    s[i] = x_1, s[i + n] = x_2;
}

\(1\) 表示这个线段存在，\(-1\) 表示这个线段不存在；s 数组记录的是端点的位置坐标，对于这个数组我们还要离散化。

sort(s + 1, s + n + 1);
int tot = unique(s + 1, s + n + 1) - s - 1;
sort(line + 1, line + n + 1, [](node a, node b) -> bool {
    return a.H < b.H;
});

然后就是建树。


void build(int u, int l, int r) {
    t[u].L = l, t[u].R = r;
    t[u].sum = t[u].tag = 0;
    if (l == r) {
        return ;
    }
    build(ls, l, mid);
    build(rs, mid + 1, r);
}

build(1, 1, tot - 1);

为什么是 tot - 1 呢？

我们已经知道，这棵线段树的每个节点都对应了一条线段。考虑将线段树上节点对应的区间和横边建立映射关系。先看对于一个叶子节点 \(x\)，建树时保证了 t[x].L = t[x].R，但其保存的信息很显然不可能只是某条线段的一个端点（如果一条线段的两个端点重合，那么它实质上仅是一个点）。再看一个节点的左右儿子，同样地，建树的时候已经保证了左右儿子的区间不会重合（交集为空），但是看这样两条相邻线段：\([1,2],[2,3]\),你会发现 \([1,2] \cap [2,3]= \{2 \}\)，也就是说左儿子的右端点和右儿子的左端点其实是重合的。

考虑把线段树每个节点x对应的区间（t[x].L, t[x].R）不变，改变区间和横边的映射关系，具体为：节点x对应 [s[t[x].L], s[t[x].R+1]] 这条横边。可以看到，这里很机智地把右端点的对应关系给改了下，于是就兼容了。

随后是我们的查询函数，相信聪明的你可以看懂。

void pushup(int u) {
    if (t[u].tag > 0) { // 是否被完全覆盖
        t[u].sum = s[t[u].R + 1] - s[t[u].L];
        return ;
    }
    if (t[u].L != t[u].R) { // 如果不是叶子节点
        t[u].sum = t[ls].sum + t[rs].sum;
    } else { // 如果是叶子节点
        t[u].sum = 0;
    }
    return ;
}

void Find(int u, ll l, ll r, int v) {
    if (s[t[u].R + 1] <= l || s[t[u].L] >= r) {
        return ;
    }
    if (l <= s[t[u].L] && s[t[u].R + 1] <= r) {
        t[u].tag += v;
        pushup(u);
        return ;
    }
    if (t[u].L == t[u].R) { // 当前已经到了叶子节点
        return ;
    }
    Find(ls, l, r, v);
    Find(rs, l, r, v);
    pushup(u);
}

总代码：

//The code was written by yifan, and yifan is neutral!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid ((l + r) >> 1)

template<typename T>
inline T read() {
    T x = 0;
    bool fg = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        fg |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return fg ? ~x + 1 : x;
}

const int N = 1e5 + 5;

int n;
ll s[N << 1];

struct node {
    int val;
    ll L, R, H;
    // val 该线段是否存在
    // L, R 左右端点
    // H 高度
} line[N << 1];

struct seg {
    int L, R, tag;
    ll sum;
    // L, R 左右短点
    // sum 被覆盖的长度
    // tag 是否被完全覆盖
} t[N << 3];

void pushup(int u) {
    if (t[u].tag > 0) {
        t[u].sum = s[t[u].R + 1] - s[t[u].L];
        return ;
    }
    if (t[u].L != t[u].R) {
        t[u].sum = t[ls].sum + t[rs].sum;
    } else {
        t[u].sum = 0;
    }
    return ;
}

void build(int u, int l, int r) {
    t[u].L = l, t[u].R = r;
    t[u].sum = t[u].tag = 0;
    if (l == r) {
        return ;
    }
    build(ls, l, mid);
    build(rs, mid + 1, r);
}

void Find(int u, ll l, ll r, int v) {
    if (s[t[u].R + 1] <= l || s[t[u].L] >= r) {
        return ;
    }
    if (l <= s[t[u].L] && s[t[u].R + 1] <= r) {
        t[u].tag += v;
        pushup(u);
        return ;
    }
    if (t[u].L == t[u].R) {
        return ;
    }
    Find(ls, l, r, v);
    Find(rs, l, r, v);
    pushup(u);
}

int main() {
    n = read<int>();
    for (int i = 1; i <= n; ++ i) {
        int x_1 = read<ll>(), y_1 = read<ll>(), x_2 = read<ll>(), y_2 = read<ll>();
        line[i] = node{1, x_1, x_2, y_1};
        line[i + n] = node{-1, x_1, x_2, y_2};
        s[i] = x_1, s[i + n] = x_2;
    }
    n <<= 1;
    sort(s + 1, s + n + 1);
    int tot = unique(s + 1, s + n + 1) - s - 1;
    sort(line + 1, line + n + 1, [](node a, node b) -> bool {
        return a.H < b.H;
    });
    build(1, 1, tot - 1);
    ll ans = 0;
    for (int i = 1; i < n; ++ i) {
        Find(1, line[i].L, line[i].R, line[i].val);
        ans += t[1].sum * (line[i + 1].H - line[i].H);
    }
    cout << ans << '\n';
    return 0;
}

再来一道模板例题。

P8648 [蓝桥杯 2017 省 A] 油漆面积 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

//The code was written by yifan, and yifan is neutral!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid ((l + r) >> 1)

template<typename T>
inline T read() {
    T x = 0;
    bool fg = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        fg |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return fg ? ~x + 1 : x;
}

const int N = 1e4 + 5;

int n, tot;
int s[N << 1];

struct Line {
    int L, R, H, val;
} line[N << 1];

struct seg {
    int L, R, tag;
    ll len;
} t[N << 3];

void build(int u, int l, int r) {
    t[u].L = l, t[u].R = r;
    t[u].tag = t[u].len = 0;
    if (l == r) {
        return ;
    }
    build(ls, l, mid);
    build(rs, mid + 1, r);
}

void pushup(int u) {
    if (t[u].tag) {
        t[u].len = s[t[u].R + 1] - s[t[u].L];
        return ;
    }
    if (t[u].L == t[u].R) {
        t[u].len = 0;
    } else {
        t[u].len = t[ls].len + t[rs].len;
    }
}

void Find(int u, int l, int r, int v) {
    if (s[t[u].R + 1] <= l || r <= s[t[u].L]) {
        return ;
    }
    if (l <= s[t[u].L] && s[t[u].R + 1] <= r) {
        t[u].tag += v;
        pushup(u);
        return ;
    }
    if (t[u].L == t[u].R) {
        return ;
    }
    Find(ls, l, r, v);
    Find(rs, l, r, v);
    pushup(u);
}

int main() {
    n = read<int>();
    for (int i = 1; i <= n; ++ i) {
        int x_1 = read<int>(), y_1 = read<int>(), x_2 = read<int>(), y_2 = read<int>();
        line[i] = Line{x_1, x_2, y_1, 1};
        line[i + n] = Line{x_1, x_2, y_2, -1};
        s[i] = x_1, s[i + n] = x_2;
    }
    n <<= 1;
    sort(s + 1, s + n + 1);
    tot = unique(s + 1, s + n + 1) - s - 1;
    build(1, 1, tot - 1);
    sort(line + 1, line + n + 1, [](Line a, Line b) -> bool {
        return a.H < b.H;
    });
    ll ans = 0;
    for (int i = 1; i < n; ++ i) {
        Find(1, line[i].L, line[i].R, line[i].val);
        ans += t[1].len * (line[i + 1].H - line[i].H);
    }
    cout << ans << '\n';
    return 0;
}

求周长并

求周长并比求面积更复杂，周长还要考虑竖着的线段的长度。

对于横边，相邻两次修改的区间覆盖长度差（就是 t[1].len 的差）加起来就是答案（不理解的自己想办法理解，反正我不理解）；

对于竖边，我们只需要记录整个区间有多少个端点（包含在线段内不算），然后用它乘上相邻两次修改的高度差即可。

代码：

//The code was written by yifan, and yifan is neutral!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid ((l + r) >> 1)

template<typename T>
inline T read() {
    T x = 0;
    bool fg = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        fg |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return fg ? ~x + 1 : x;
}

const int N = 5010;

int n;
int s[N << 1];

struct Line {
    int L, R, H, val;
} line[N << 1];

struct seg {
    int L, R, tag, cnt;
    ll len;
    bool lc, rc;
} t[N << 3];

void build(int u, int l, int r) {
    t[u].L = l, t[u].R = r;
    t[u].tag = t[u].len = t[u].cnt = 0;
    t[u].lc = t[u].rc = false;
    if (l == r) {
        return ;
    }
    build(ls, l, mid);
    build(rs, mid + 1, r);
}

void pushup(int u) {
    if (t[u].tag) {
        t[u].len = s[t[u].R + 1] - s[t[u].L];
        t[u].lc = t[u].rc = true;
        t[u].cnt = 1;
        return ;
    }
    if (t[u].L == t[u].R) {
        t[u].len = 0;
        t[u].lc = t[u].rc = false;
        t[u].cnt = 0;
    } else {
        t[u].len = t[ls].len + t[rs].len;
        t[u].lc = t[ls].lc, t[u].rc = t[rs].rc;
        t[u].cnt = t[ls].cnt + t[rs].cnt;
        if (t[ls].rc && t[rs].lc) {
            -- t[u].cnt;
        }
    }
}

void Find(int u, int l, int r, int v) {
    if (r <= s[t[u].L] || s[t[u].R + 1] <= l) {
        return ;
    }
    if (l <= s[t[u].L] && s[t[u].R + 1] <= r) {
        t[u].tag += v;
        pushup(u);
        return ;
    }
    if (t[u].L == t[u].R) {
        return ;
    }
    Find(ls, l, r, v);
    Find(rs, l, r, v);
    pushup(u);
}

int main() {
    n = read<int>();
    for (int i = 1, x_1, y_1, x_2, y_2; i <= n; ++ i) {
        x_1 = read<int>(), y_1 = read<int>(), x_2 = read<int>(), y_2 = read<int>();
        line[i] = Line{x_1, x_2, y_1, 1};
        line[i + n] = Line{x_1, x_2, y_2, -1};
        s[i] = x_1, s[i + n] = x_2;
    }
    n <<= 1;
    sort(s + 1, s + n + 1);
    int tot = unique(s + 1, s + n + 1) - s - 1;
    build(1, 1, tot - 1);
    sort(line + 1, line + n + 1, [](Line a, Line b) -> bool {
        if (a.H == b.H) return a.val > b.val;
        return a.H < b.H;
    });
    ll ans = 0, pre = 0;
    for (int i = 1; i < n; ++ i) {
        Find(1, line[i].L, line[i].R, line[i].val);
        ans += abs(pre - t[1].len);
        pre = t[1].len;
        ans += 2 * t[1].cnt * (line[i + 1].H - line[i].H);
    }
    ans += line[n].R - line[n].L;
    cout << ans << '\n';
    return 0;
}

上模板题！

P1856 [IOI1998] [USACO5.5] 矩形周长Picture - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

标签：ch,return,int,线段,笔记,学习,read,扫描线,line
From： https://www.cnblogs.com/yifan0305/p/17609438.html

相关文章

  • 笔记|《Python数据分析基础》
    python基础StrategyforFindingaRegexWeneedastrategytofindaregexthatmatchesallthewinnersbutnoneofthelosers.Icameupwiththisapproach:Generateapoolofregexparts:smallregexesofafewcharacters,suchasoror."bu"&......
  • 《Java编程思想第四版》学习笔记05
    6.9.1继承初始化我们有必要对整个初始化过程有所认识，其中包括继承，对这个过程中发生的事情有一个整体性的概念。请观察下述代码：//:Beetle.java//Thefullprocessofinitialization.classInsect{inti=9;intj;Insect(){prt("i="+i+",j="+j);j=39;......
  • Tarjan 系列学习笔记
    最近在复习提高算法，所以学习复习笔记写的就比较多。Tarjan系列的算法主要针对于图论而言。Part\(1\)缩点缩点算是Tarjan算法最广泛的应用了。先讲拓扑序。在一个有向图中，若此图无环，我们称这个图是有向无环图，也叫DAG，我们可以用拓扑排序解决许多图上问题，简单思路是先把入......
  • 七月学习之Iptables连接追踪state
    7、Iptables连接追踪state7.1、什么是连接追踪state(conntrack)连接追踪，顾名思义，就是跟踪(并记录)连接的状态如下图:是一台IP地址为10.1.1.2的linux机器，我们能看到这台机器上有三条连接1、机器访问外部HTTP服务的连接(目的端口80)2、外部访问机器内FTP服务的连接(目的端口21)3......
  • 【JAVA】如何学好Java并调整学习过程中的心态
    学习Java是一项挑战性而又值得追求的目标。掌握Java编程语言，不仅可以为您的职业发展增添新的机会，还能让您体验到编程的乐趣。本文将为您提供学习Java的有效方法，并探讨调整学习过程中心态的关键。第一步：建立坚实的基础在开始学习Java之前，建立坚实的基础至关重要。学习Java编程语言......
  • 深度学习编译器前端技术概述
    AI编译器在前端经常会做一些静态分析，方便在前端做一些优化：自动微分等。中间表示（IntermediateRepresentation,IR）IR是编译器用于表示源代码的数据结构或代码，是程序编译过程中介于源语言和目标语言之间的程序表示。几乎所有的编译器都需要某种形式的中间表示，来对被分析、转换......
  • 深信服行为管理AC配置笔记
    深信服行为管理AC配置，可以直接参考官网原文：https://support.sangfor.com.cn/productDocument/read?product_id=22&version_id=907&category_id=244007 步骤1.通过默认IP登录设备，比如通过LAN口登录设备，LAN口的默认IP是10.251.251.251/24，在电脑上配置一个此网段的IP地址，通过http......
  • 一些笔记同步软件，notion替代，开源笔记软件
    StandardNotes|End-To-EndEncryptedNotesApphttps://www.bookstackapp.com/https://www.qownnotes.org/https://github.com/zadam/triliumFlowUs息流官网-新一代知识管理与协同平台,在线文档笔记知识库,项目管理协作Releases·toeverything/AFFiNE·GitHubAFFiNE......
  • 前端学习笔记202306学习笔记第四十八天-react-admin marmelab之6
            ......
  • 前端学习笔记202306学习笔记第四十八天-react-admin marmelab之5
          ......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99