『线段树扫描线算法』简单理解

Question1

给定若干个矩形，线矩形的面积并。分别用$O(n^2)$级别和$O(nlogn)$级别的算法解决。

我们的做法是对矩形的纵坐标进行离散化，得到离散化后的坐标$y_1,y_2,...,y_m.$用$val(y)$表示原始坐标值。这样我们就可以将浮点数转化为了方便处理的整数，有利于数组下表的表示。

我们用数组$c[i](i\in [1,m))$存储在当前情况下，$y_{i+1}-y_i$的纵区间的覆盖情况。$0$表示没有覆盖，$k$表示被覆盖了$k$次，不可能出现小于$0$的情况，因为只有“被覆盖的次数”和“没有覆盖”两种情况的存在。

现在我们回到这个面积计算的题中：我们可以将一个矩形的左右边界分别处理，左边界带来的是“正影响”，会对答案做出纵区间大小的贡献；右边界带来的是“负影响”，会使先前的正影响消失。这也是上面c数组都是非负数的原因。因此我们可以将左右边界分开，用四元组表示(横坐标，上边界，下边界，影响)；用$(x_i,y_{1,i},y_{2,i},f_i)$表示。这里的影响指“正影响”和“负影响”，分别规定为1和-1.

得到若干个四元组以后，我们需要对$x$坐标进行排序，那么我们得到了一个$x$坐标递增的“竖线”。枚举每一个四元组，若当前的影响为正，则令$c[k](k\in [y_{1,i},y_{2,i}))$加上1，表示这个纵区间产生了影响；反之，则减去$1$来消除这一个影响。

现在我们需要统计答案，当$i>1$时，不止是一条竖线，形成的更是一个矩形，我们可以用$sum$表示横坐标到$x_i(i>1)$的答案。其中$$sum=\sum _{i=1}^{m-1}(val(y+1)-val(y))\ast (x_i-x_{i-1}).$$

此时可以用$O(n^2)$算法直接得到了。代码1就采用了这个方法。

我们知道，每一次$c$数组的更改是一个连续的区间的修改，即对应了一个区间修改操作——我们可以利用这一特性，采用线段树来进行维护。这样就避免了一次暴力的扫描，将$O(n^2)$的时间复杂度优化到了$O(nlogn)$.

Question2

有$n(n\in [1,10^5])$个点，求一个长为$w$，宽为$h$的矩形能覆盖多少个点；且边界上的点不算。矩形的点一定要是整数。

如果我们要求出这一个矩形的右上角在哪一个区间内能够包含这个点，若这个点的坐标为$(x-0.5,y-0.5)$,则合法的区间是$(x,y)$到$(x+w-1,y+h-1)$.显然，对坐标的点平移不会对答案产生影响；因为每一个点都平移则相对的位置不发生变化，而且能使矩形的边界包括这些点。

现在我们需要求矩形的最大重叠部分。同样可以使用上述扫描线的思路，仅仅将最后的“区间求和”改为了“区间最值”，这同样在线段树的操作范围以内。可以用$O(nlogn)$的时间内快速解决。

Code

Question1:

#include <map> #include <cstring> #include <cstdio> #include <iostream> #include <algorithm> using namespace std; struct node { double x,y1,y2; int k; }; bool cmp(node p1, node p2) { return p1.x < p2.x; } int n,m = 0, cnt = 0, tot = 0; double x1,x2,y1,y2; int c[200000]; node a[200000]; double b[200000]; double pos[200000]; map<double,int> num; void work(void) { m = 0, cnt = 0, tot ++; memset(c, 0, sizeof c); memset(b, 0, sizeof b); memset(pos, 0, sizeof pos); num.clear(); double ans = 0.000; scanf("%d",&n); if (n == 0) exit(0); for (int i=1;i<=n;++i) { scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2); a[++m] = node{x1,y1,y2,+1}, b[m] = y1; a[++m] = node{x2,y1,y2,-1}, b[m] = y2; } sort(b+1,b+m+1); for (int i=1;i<=m;++i) if (num[b[i]] == 0) { num[b[i]] = ++cnt; pos[cnt] = b[i]; } sort(a+1, a+m+1, cmp); for (int i=num[a[1].y1];i<num[a[1].y2];++i) c[i] += a[1].k; for (int i=2;i<=m;++i) { for (int j=1;j<=m;++j) if (c[j] > 0) ans += (a[i].x - a[i-1].x) * (pos[j+1]-pos[j]); for (int j=num[a[i].y1];j<num[a[i].y2];++j) c[j] += a[i].k; } printf("Test case #%d\n", tot); printf("Total explored area: %.2lf\n\n", ans); return; } int main(void) { freopen("atlantis.in","r",stdin); freopen("atlantis.out","w",stdout); while (true) work(); return 0; }

Question2

#include <cstring> #include <iostream> #include <cstdio> #include <algorithm> #define int long long inline int read(void) { int s = 0, w = 1;char c = getchar(); while (c<'0' || c>'9') {if (c == '-') w = -1; c = getchar();} while (c>='0' && c<='9') s = s*10+c-48,c = getchar(); return s*w; } using namespace std; struct node { int x,y1,y2,c; friend bool operator < (node p1, node p2) { if (p1.x == p2.x) return p1.c < p2.c; return p1.x < p2.x; } } a[200000]; int n,W,H,m; int p[200000]; int y1[2000000]; int y2[2000000]; int bri[200000]; void discre(void) { sort(bri+1, bri+n+1); for (int i=1;i<=n;++i) if (bri[i] ^ bri[i-1] || i == 1) p[++m] = bri[i]; for (int i=1;i<=n;++i) { y1[i] = lower_bound(p+1, p+m+1, a[i].y1)-p; y2[i] = lower_bound(p+1, p+m+1, a[i].y2)-p; } return; } struct Segment { int l,r,add,ans; } tree[200000]; void clear(void) { m = 0; memset(tree, 0, sizeof tree); return; } void Build(int p,int l,int r) { tree[p].l = l; tree[p].r = r; if (l == r) return; int mid = l+r >> 1; Build(p*2,l,mid); Build(p*2+1,mid+1,r); return; } void spread(int p) { tree[p*2].ans += tree[p].add; tree[p*2+1].ans += tree[p].add; tree[p*2].add += tree[p].add; tree[p*2+1].add += tree[p].add; tree[p].add = 0; return; } void add(int p,int l,int r,int v) { if (l <= tree[p].l && r >= tree[p].r) { tree[p].ans += v; tree[p].add += v; return; } if (tree[p].add) spread(p); int mid = tree[p].l+tree[p].r >> 1; if (l <= mid) add(p*2,l,r,v); if (r > mid) add(p*2+1,l,r,v); tree[p].ans = max(tree[p*2].ans,tree[p*2+1].ans); return; } void work(void) { W = read(); H = read(); clear(); for (int i=1;i<=n;++i) { int x = read(), y = read(), c = read(); a[i*2-1] = node{x,y,y+H-1,c}; a[i*2] = node{x+W,y,y+H-1,-c}; bri[i*2-1] = y; bri[i*2] = y+H-1; } n *= 2; sort(a+1,a+n+1); discre(); Build(1,1,m); int ans = 0; for (int i=1;i<=n;++i) { add(1,y1[i],y2[i],a[i].c); ans = max(tree[1].ans,ans); } printf("%lld\n", ans); return; } signed main(void) { freopen("stars.in","r",stdin); freopen("stars.out","w",stdout); while (cin>>n) work(); return 0; }