经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » Python3 » 查看文章
「学习笔记」扫描线
来源:cnblogs  作者:yi_fan0305  时间:2023/8/7 9:14:25  对本文有异议

什么是扫描线?顾名思义,一根用来扫描的线

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

下面我们用例题来引入。

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

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

  1. 暴力的进行覆盖扫描

  2. 容斥

  3. 线段树

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

过程

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

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

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

实现

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

  1. struct node {
  2. int val;
  3. ll L, R, H;
  4. // val 该线段是否存在
  5. // L, R 左右端点
  6. // H 高度
  7. } line[N << 1];
  8. struct seg {
  9. int L, R, tag;
  10. ll sum;
  11. // L, R 左右短点
  12. // sum 被覆盖的长度
  13. // tag 是否被完全覆盖
  14. } t[N << 3];

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

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

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

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

然后就是建树。

  1. void build(int u, int l, int r) {
  2. t[u].L = l, t[u].R = r;
  3. t[u].sum = t[u].tag = 0;
  4. if (l == r) {
  5. return ;
  6. }
  7. build(ls, l, mid);
  8. build(rs, mid + 1, r);
  9. }
  10. 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]] 这条横边。可以看到,这里很机智地把右端点的对应关系给改了下,于是就兼容了。

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

  1. void pushup(int u) {
  2. if (t[u].tag > 0) { // 是否被完全覆盖
  3. t[u].sum = s[t[u].R + 1] - s[t[u].L];
  4. return ;
  5. }
  6. if (t[u].L != t[u].R) { // 如果不是叶子节点
  7. t[u].sum = t[ls].sum + t[rs].sum;
  8. } else { // 如果是叶子节点
  9. t[u].sum = 0;
  10. }
  11. return ;
  12. }
  13. void Find(int u, ll l, ll r, int v) {
  14. if (s[t[u].R + 1] <= l || s[t[u].L] >= r) {
  15. return ;
  16. }
  17. if (l <= s[t[u].L] && s[t[u].R + 1] <= r) {
  18. t[u].tag += v;
  19. pushup(u);
  20. return ;
  21. }
  22. if (t[u].L == t[u].R) { // 当前已经到了叶子节点
  23. return ;
  24. }
  25. Find(ls, l, r, v);
  26. Find(rs, l, r, v);
  27. pushup(u);
  28. }

总代码:

  1. //The code was written by yifan, and yifan is neutral!!!
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. typedef long long ll;
  5. #define bug puts("NOIP rp ++!");
  6. #define ls (u << 1)
  7. #define rs (u << 1 | 1)
  8. #define mid ((l + r) >> 1)
  9. template<typename T>
  10. inline T read() {
  11. T x = 0;
  12. bool fg = 0;
  13. char ch = getchar();
  14. while (ch < '0' || ch > '9') {
  15. fg |= (ch == '-');
  16. ch = getchar();
  17. }
  18. while (ch >= '0' && ch <= '9') {
  19. x = (x << 3) + (x << 1) + (ch ^ 48);
  20. ch = getchar();
  21. }
  22. return fg ? ~x + 1 : x;
  23. }
  24. const int N = 1e5 + 5;
  25. int n;
  26. ll s[N << 1];
  27. struct node {
  28. int val;
  29. ll L, R, H;
  30. // val 该线段是否存在
  31. // L, R 左右端点
  32. // H 高度
  33. } line[N << 1];
  34. struct seg {
  35. int L, R, tag;
  36. ll sum;
  37. // L, R 左右短点
  38. // sum 被覆盖的长度
  39. // tag 是否被完全覆盖
  40. } t[N << 3];
  41. void pushup(int u) {
  42. if (t[u].tag > 0) {
  43. t[u].sum = s[t[u].R + 1] - s[t[u].L];
  44. return ;
  45. }
  46. if (t[u].L != t[u].R) {
  47. t[u].sum = t[ls].sum + t[rs].sum;
  48. } else {
  49. t[u].sum = 0;
  50. }
  51. return ;
  52. }
  53. void build(int u, int l, int r) {
  54. t[u].L = l, t[u].R = r;
  55. t[u].sum = t[u].tag = 0;
  56. if (l == r) {
  57. return ;
  58. }
  59. build(ls, l, mid);
  60. build(rs, mid + 1, r);
  61. }
  62. void Find(int u, ll l, ll r, int v) {
  63. if (s[t[u].R + 1] <= l || s[t[u].L] >= r) {
  64. return ;
  65. }
  66. if (l <= s[t[u].L] && s[t[u].R + 1] <= r) {
  67. t[u].tag += v;
  68. pushup(u);
  69. return ;
  70. }
  71. if (t[u].L == t[u].R) {
  72. return ;
  73. }
  74. Find(ls, l, r, v);
  75. Find(rs, l, r, v);
  76. pushup(u);
  77. }
  78. int main() {
  79. n = read<int>();
  80. for (int i = 1; i <= n; ++ i) {
  81. int x_1 = read<ll>(), y_1 = read<ll>(), x_2 = read<ll>(), y_2 = read<ll>();
  82. line[i] = node{1, x_1, x_2, y_1};
  83. line[i + n] = node{-1, x_1, x_2, y_2};
  84. s[i] = x_1, s[i + n] = x_2;
  85. }
  86. n <<= 1;
  87. sort(s + 1, s + n + 1);
  88. int tot = unique(s + 1, s + n + 1) - s - 1;
  89. sort(line + 1, line + n + 1, [](node a, node b) -> bool {
  90. return a.H < b.H;
  91. });
  92. build(1, 1, tot - 1);
  93. ll ans = 0;
  94. for (int i = 1; i < n; ++ i) {
  95. Find(1, line[i].L, line[i].R, line[i].val);
  96. ans += t[1].sum * (line[i + 1].H - line[i].H);
  97. }
  98. cout << ans << '\n';
  99. return 0;
  100. }

再来一道模板例题。

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

  1. //The code was written by yifan, and yifan is neutral!!!
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. typedef long long ll;
  5. #define bug puts("NOIP rp ++!");
  6. #define ls (u << 1)
  7. #define rs (u << 1 | 1)
  8. #define mid ((l + r) >> 1)
  9. template<typename T>
  10. inline T read() {
  11. T x = 0;
  12. bool fg = 0;
  13. char ch = getchar();
  14. while (ch < '0' || ch > '9') {
  15. fg |= (ch == '-');
  16. ch = getchar();
  17. }
  18. while (ch >= '0' && ch <= '9') {
  19. x = (x << 3) + (x << 1) + (ch ^ 48);
  20. ch = getchar();
  21. }
  22. return fg ? ~x + 1 : x;
  23. }
  24. const int N = 1e4 + 5;
  25. int n, tot;
  26. int s[N << 1];
  27. struct Line {
  28. int L, R, H, val;
  29. } line[N << 1];
  30. struct seg {
  31. int L, R, tag;
  32. ll len;
  33. } t[N << 3];
  34. void build(int u, int l, int r) {
  35. t[u].L = l, t[u].R = r;
  36. t[u].tag = t[u].len = 0;
  37. if (l == r) {
  38. return ;
  39. }
  40. build(ls, l, mid);
  41. build(rs, mid + 1, r);
  42. }
  43. void pushup(int u) {
  44. if (t[u].tag) {
  45. t[u].len = s[t[u].R + 1] - s[t[u].L];
  46. return ;
  47. }
  48. if (t[u].L == t[u].R) {
  49. t[u].len = 0;
  50. } else {
  51. t[u].len = t[ls].len + t[rs].len;
  52. }
  53. }
  54. void Find(int u, int l, int r, int v) {
  55. if (s[t[u].R + 1] <= l || r <= s[t[u].L]) {
  56. return ;
  57. }
  58. if (l <= s[t[u].L] && s[t[u].R + 1] <= r) {
  59. t[u].tag += v;
  60. pushup(u);
  61. return ;
  62. }
  63. if (t[u].L == t[u].R) {
  64. return ;
  65. }
  66. Find(ls, l, r, v);
  67. Find(rs, l, r, v);
  68. pushup(u);
  69. }
  70. int main() {
  71. n = read<int>();
  72. for (int i = 1; i <= n; ++ i) {
  73. int x_1 = read<int>(), y_1 = read<int>(), x_2 = read<int>(), y_2 = read<int>();
  74. line[i] = Line{x_1, x_2, y_1, 1};
  75. line[i + n] = Line{x_1, x_2, y_2, -1};
  76. s[i] = x_1, s[i + n] = x_2;
  77. }
  78. n <<= 1;
  79. sort(s + 1, s + n + 1);
  80. tot = unique(s + 1, s + n + 1) - s - 1;
  81. build(1, 1, tot - 1);
  82. sort(line + 1, line + n + 1, [](Line a, Line b) -> bool {
  83. return a.H < b.H;
  84. });
  85. ll ans = 0;
  86. for (int i = 1; i < n; ++ i) {
  87. Find(1, line[i].L, line[i].R, line[i].val);
  88. ans += t[1].len * (line[i + 1].H - line[i].H);
  89. }
  90. cout << ans << '\n';
  91. return 0;
  92. }

求周长并

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

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

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

代码:

  1. //The code was written by yifan, and yifan is neutral!!!
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. typedef long long ll;
  5. #define bug puts("NOIP rp ++!");
  6. #define ls (u << 1)
  7. #define rs (u << 1 | 1)
  8. #define mid ((l + r) >> 1)
  9. template<typename T>
  10. inline T read() {
  11. T x = 0;
  12. bool fg = 0;
  13. char ch = getchar();
  14. while (ch < '0' || ch > '9') {
  15. fg |= (ch == '-');
  16. ch = getchar();
  17. }
  18. while (ch >= '0' && ch <= '9') {
  19. x = (x << 3) + (x << 1) + (ch ^ 48);
  20. ch = getchar();
  21. }
  22. return fg ? ~x + 1 : x;
  23. }
  24. const int N = 5010;
  25. int n;
  26. int s[N << 1];
  27. struct Line {
  28. int L, R, H, val;
  29. } line[N << 1];
  30. struct seg {
  31. int L, R, tag, cnt;
  32. ll len;
  33. bool lc, rc;
  34. } t[N << 3];
  35. void build(int u, int l, int r) {
  36. t[u].L = l, t[u].R = r;
  37. t[u].tag = t[u].len = t[u].cnt = 0;
  38. t[u].lc = t[u].rc = false;
  39. if (l == r) {
  40. return ;
  41. }
  42. build(ls, l, mid);
  43. build(rs, mid + 1, r);
  44. }
  45. void pushup(int u) {
  46. if (t[u].tag) {
  47. t[u].len = s[t[u].R + 1] - s[t[u].L];
  48. t[u].lc = t[u].rc = true;
  49. t[u].cnt = 1;
  50. return ;
  51. }
  52. if (t[u].L == t[u].R) {
  53. t[u].len = 0;
  54. t[u].lc = t[u].rc = false;
  55. t[u].cnt = 0;
  56. } else {
  57. t[u].len = t[ls].len + t[rs].len;
  58. t[u].lc = t[ls].lc, t[u].rc = t[rs].rc;
  59. t[u].cnt = t[ls].cnt + t[rs].cnt;
  60. if (t[ls].rc && t[rs].lc) {
  61. -- t[u].cnt;
  62. }
  63. }
  64. }
  65. void Find(int u, int l, int r, int v) {
  66. if (r <= s[t[u].L] || s[t[u].R + 1] <= l) {
  67. return ;
  68. }
  69. if (l <= s[t[u].L] && s[t[u].R + 1] <= r) {
  70. t[u].tag += v;
  71. pushup(u);
  72. return ;
  73. }
  74. if (t[u].L == t[u].R) {
  75. return ;
  76. }
  77. Find(ls, l, r, v);
  78. Find(rs, l, r, v);
  79. pushup(u);
  80. }
  81. int main() {
  82. n = read<int>();
  83. for (int i = 1, x_1, y_1, x_2, y_2; i <= n; ++ i) {
  84. x_1 = read<int>(), y_1 = read<int>(), x_2 = read<int>(), y_2 = read<int>();
  85. line[i] = Line{x_1, x_2, y_1, 1};
  86. line[i + n] = Line{x_1, x_2, y_2, -1};
  87. s[i] = x_1, s[i + n] = x_2;
  88. }
  89. n <<= 1;
  90. sort(s + 1, s + n + 1);
  91. int tot = unique(s + 1, s + n + 1) - s - 1;
  92. build(1, 1, tot - 1);
  93. sort(line + 1, line + n + 1, [](Line a, Line b) -> bool {
  94. if (a.H == b.H) return a.val > b.val;
  95. return a.H < b.H;
  96. });
  97. ll ans = 0, pre = 0;
  98. for (int i = 1; i < n; ++ i) {
  99. Find(1, line[i].L, line[i].R, line[i].val);
  100. ans += abs(pre - t[1].len);
  101. pre = t[1].len;
  102. ans += 2 * t[1].cnt * (line[i + 1].H - line[i].H);
  103. }
  104. ans += line[n].R - line[n].L;
  105. cout << ans << '\n';
  106. return 0;
  107. }

上模板题!

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

原文链接:https://www.cnblogs.com/yifan0305/p/17609438.html

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号