扫描线 亚特兰蒂斯

本文主要是介绍扫描线 亚特兰蒂斯，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：247. 亚特兰蒂斯

算法分析

只说细节。

这道题目不是特别严格的线段树，因为线段树维护的信息具有区间可合并性，这道题目想了很久想不出可以区间直接合并的信息。我们在这里维护的是离散化后表示小段的数组，设为$a[]$吧，对于一个边界的两个纵坐标，设为$y1$和$y2$，离散化后的结果为$[al,ar]$，这是点，如果要对应到小段，那么则是$[al,ar-1]$。

在每个区间结点上，设cnt表示该区间被完整扫过的次数，这里强调下，是完整扫过，那些子区间被扫过但本身没被完整扫过的不能累加。因此，满足不了区间可合并的特性。但是因为在树上，我们在更新线段树的时候，可以将结果从下往上累加，在每个结点上用len表示该区间被扫描线覆盖的长度。下面是重点：

当某个区间结点的cnt>0，则$tr[p].len=val[ar+1]-val[al]$，因为线段树中维护的是小段，要计算的话，得转移到点上直接相减，所以右端点是$ar+1$。

当某个区间结点的cnt=0，则它的len值是其左右儿子的len值之和。如果该点是叶结点，则len值重置为0。

if (tr[p].cnt)tr[p].len = val[ar+1] - val[al];else if (al != ar)tr[p].len = tr[2*p].len + tr[2*p+1].len;else tr[p].len = 0; 

该边界被扫描线覆盖的长度就是$tr[1].len$。不需要查询。事实上，这种做法下，查询了反而是错的。如果查询$[al,ar]$，结果代表扫描线在区间$[al,ar+1]$被覆盖的长度，和要求不符，如果查询$[1,cnt-1]$，有可能该结点的cnt为0，造成漏查。

根据以上分析，就无需下传标记了。

离散化的时候，除了要记录离散化后的整数对应原来的实数，还要记录原来的实数对应的整数。后者用map实现。也可以在lsh[]中用$lower\_bound$重新查询下位次。

map<double, int> lshval;
sort(lsh + 1, lsh + t + 1);
int cnt = unique(lsh + 1, lsh + t + 1) - lsh - 1;
for (int i = 1; i <= t; ++i)
{double tem = aa[i];a[i] = lower_bound(lsh + 1, lsh + cnt + 1, aa[i]) - lsh;val[a[i]] = tem;lshval[tem] = a[i];
}	

注意：离散化之前要对lsh数组排序。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <map>
#include <vector>
using namespace std;
#define ll long long 
const int N = 1e4 + 10;
double aa[2*N], val[2*N], lsh[2*N];
int a[2*N];
int n;
map<double, int> lshval;
struct dot
{double x, y1, y2;int id;
}d[2*N];
struct SegmentTree
{double len;int cnt;
}tr[8*N];
double relf()
{double x = 0, y = 0.1, f = 1; char c = getchar();while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}while (c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}if (c == '.'){c = getchar();while (c >= '0' && c <= '9'){x += y * (c - '0'); y /= 10; c = getchar();} }return x * f; 
}
bool cmp(dot a, dot b)
{return a.x < b.x;
}
void szbuild(int p, int l, int r)
{tr[p].len = tr[p].cnt = 0;if (l == r) return;int mid = (l + r) >> 1;szbuild(2 * p, l, mid);szbuild(2 * p + 1, mid + 1, r);	
}
void szchange(int p, int al, int ar, int ql, int qr, int num)
{if (ql > ar || qr < al) return;  // 完全没交集，直接返回 if (ql <= al && ar <= qr){tr[p].cnt += num;if (tr[p].cnt)tr[p].len = val[ar+1] - val[al];else if (al != ar)tr[p].len = tr[2*p].len + tr[2*p+1].len;else tr[p].len = 0;  // 没有覆盖了，叶节点置为0 ，这点很重要  return;} int mid = (al + ar) >> 1;szchange(2 * p, al, mid, ql, qr, num);szchange(2 * p + 1, mid + 1, ar, ql, qr, num);if (tr[p].cnt)tr[p].len = val[ar+1] - val[al];else if (al != ar)tr[p].len = tr[2*p].len + tr[2*p+1].len;else tr[p].len = 0;  // 
}
int main()  // 标记不下传  
{int T = 0;while (1){++T;scanf("%d", &n);if (!n) break;int t = 0;double ax, ay, bx, by;for (int i = 1; i <= 2 * n; i += 2){ax = relf(); ay = relf(); bx = relf(); by = relf();d[i].x   = ax; d[i].y1   = ay;  d[i].y2   = by; d[i].id = 1;d[i+1].x = bx; d[i+1].y1 = ay;  d[i+1].y2 = by; d[i+1].id = -1;aa[++t] = ay; aa[++t] = by;}// 离散化  	memcpy(lsh, aa, sizeof(aa));sort(lsh + 1, lsh + t + 1);int cnt = unique(lsh + 1, lsh + t + 1) - lsh - 1;for (int i = 1; i <= t; ++i){double tem = aa[i];a[i] = lower_bound(lsh + 1, lsh + cnt + 1, aa[i]) - lsh;val[a[i]] = tem;lshval[tem] = a[i];}	// 建线段树维护小段，第i小段代表段val[i+1] - val[i]// 总共有cnt-1段  szbuild(1, 1, cnt - 1);// double ans = 0; sort(d + 1, d + 2 * n + 1, cmp);  // 按照x坐标排序  for (int i = 1; i <= 2 * n - 1; ++i){// [ql, qr]区间是要更新的区间  int ql = lshval[d[i].y1], qr = lshval[d[i].y2] - 1;	szchange(1, 1, cnt - 1, ql, qr, d[i].id);ans += (d[i+1].x - d[i].x) * tr[1].len;}printf("Test case #%d\n", T);printf("Total explored area: %.2lf\n\n", ans);}return 0;
}

反思与总结

1. 码代码的时候要集中精力，第一遍的错误，很难发现纠正。尽量一遍过。

2. 注意快读正负实型的写法。

这篇关于扫描线 亚特兰蒂斯的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---