扫描线周长并

· · 题解

上次做了矩形面积并之后，偶然看到了这个周长并，顺手做完后写了本文。

提示：如果你没有看过我的那篇 算法学习笔记-扫描线，那请先去看那个，里面讲了扫描线的基础和面积并的求法。

首先，我们需要明确扫描线矩形周长并的思想。

类比一下面积并：

面积并是将多边形切成一个个互不相交的矩形，然后将其面积简单加和。

那周长并可以怎么做呢？

由于这里是扫描线算法，所以这个方法一定与切割有关。

建议思考一下，下面是方法。

我们将多边形切成一个个面积交为 0 的矩形，然后将其周长加和，每次减去两个相邻矩形重叠的长度。

这个方法看上去完全可以，但是仔细想想，我们要如何实现呢？

我们的扫描线移动是依靠边的增减，也就是线段树的区间加减来实现的，因此我们可以这样处理：

首先，我们要算每个矩形的周长。

这里就遇到了一个问题。

之前的扫描线板子只能让我们知道整个数轴上被覆盖的总长度，这对于不需要管其内部形状的面积并是完全够用的。

但是现在是需要求周长，那么这样的信息就完全不够了，我们还需要知道覆盖的内部是什么情况。

这就需要维护一个新的信息：整个区间上的端点个数。

为什么？我们把一批底相同的矩形（也就是同一次切割产生的矩形）拿出来，看看它的周长由什么组成。

首先就是与扫描线平行的部分，我们只需要将整个数轴上的覆盖长度乘二即可。

然后是与扫描线垂直的部分，这里就用到了整个区间的端点个数。

想象一下，一条扫描线在移动，上面有几个点一起移动，然后看看这些点的轨迹。

算了，言传很难，我传个图吧。

上面的是动之前的扫描线

这是动后的。

深灰色的是扫描线没有被覆盖的部分（参考线）

橙色的是扫描线上的点。

粉色的是点运动的轨迹。

浅灰色的是扫过的面积。

黄色的是扫描线被覆盖的区域。

我想这样应该就能明白我的意思了吧。

我们要求的矩形周长便是粉色的加上黄色的。

明白了吗？

前面说的与扫描线平行的部分，其实就是黄色的部分。

显然，就是被覆盖的长度的二倍。

然后与扫描线垂直的部分，就是粉色的部分。

只要用整个扫描线上端点的数目乘移动的距离，就是这部分的总长度。

这样，我们就能求出任何一批矩形的周长了。

然后就是如何减去重叠的部分了。

还是以图为例：

在处理某条边的变动之前，我们的矩形是这样的：

在处理完之后，我们的扫描线变成了右边的那样：

这里我将处理后的扫描线和之前的扫描线分离开了，更方便观察，但是事实上这里没有任何扫描线的移动。

而绿色的那一条便是我们这次新覆盖的一段。

我们来找找哪一部分是重叠的。

显然，就是我们处理前的长度。

那如果我们是去掉了一段，会是怎么样呢？

看图：

红色的是这次实际去掉的覆盖区域。

显然，这时重叠的区域就是我们处理后的长度。

总而言之，重叠的区域长度就是我们处理前后较短的那个的长度。

因为我们减去的事实上是两条线重合的部分，所以我们减得时候要减二倍。

自此，我们就完成了具体的思路。

但是，很可能会有人疑惑：如果是有增有减，那怎么办呢？

确实，我们之前的结论只适合单独增或减的情况，而二者都有的情况十分复杂，我们没有办法处理。

但是，俗话说得好，解决不了问题，就解决提出问题的人。

换句话说，我们只要让它每次都是单独的增加或者是减少，那不就没有问题了吗？

所以，我们只需要每条需要处理的边单独视作一次操作，让同一条线上的两个边也分别进行切割，就能解决这个问题了。

但是，有的人可能要问了：这样不会多出来一个宽度为 0 的矩形吗？

首先，如果我们是求面积并，那我们就不用担心这种不会影响答案的矩形。

但我们是周长并，所以这个问题值得深思。

首先告诉你答案：不会影响。

自行思考一下为什么，下面会有解释。

有图有真相，放图：

左边的线是我们处理前的，中间的是一个中间状态（也就是宽度为 0 的矩形，两条边重合了），右面是处理后的状态。

我们不妨设一开始覆盖长度为 l_0，增加的那一段设为 \Delta l_1，减少的那一段（长度）设为 \Delta l_2。

然后很容易得出，中间状态的长度就是 l_0+\Delta l_1，而处理完的那一段长度就是 l_0+\Delta l_1-\Delta l_2。

我们按照常识算一下这中间应该减去的长度：

2(l_0-\Delta l_2)

那么，根据我们的规律，看一下我们会减去多少：

2\times \min(l_0,l_0+\Delta l_1)+2\times\min(l_0+\Delta l_1,l_0+\Delta l_1 - \Delta l_2)

化简一下，也就是：

2\times(2l_0+\Delta l_1-\Delta l_2)

不一样？别急，还有一部分没算上。

我们多算的那一个宽度为 0 的矩形还没算上呢。

它的宽度是 0，所以我们只需要考虑它平行于扫描线的部分就行了。

2\times(l_0+\Delta l_1)

我们将减去的长度减去多算的长度（相当于负数加正数，也就是绝对值相减），得到这个：

2(l_0-\Delta l_2)

完美。

综上所述，这个中间状态不会影响我们的答案。

休息一下，接下来是代码。

由于我们需要维护区间内的端点个数，所以我们需要在我们的板子里面加上一些东西。

首先，我们仍然是利用标记永久化，这个不用动。

我们的 pushup 函数将会变成这样：

void pushup(void) {
        if (cover > 0) {  // 完全覆盖
            length= R - L + 1;
            num= 0;
            lcover= rcover= true;
            return;
        }
        if (lc == nullptr || rc == nullptr) {  // 没有覆盖且没孩子
            length= 0;
            num= 0;
            lcover= rcover= false;
        } else {  // 一般
            length= lc->length + rc->length;
            num= lc->num + rc->num;
            if (lc->rcover != rc->lcover) {
                ++num;
            }
            lcover= lc->lcover;
            rcover= rc->rcover;
            if (lc->lc == rc->rc && lc->cover == 0&&rc->cover==0) {
                delete lc;
                delete rc;
                lc= rc= nullptr;
            }
        }
    }

这里面多了几个你没见过的变量，这里列一下它们的意义：

cover：实际上就是上次的 time。

lcover（rcover）：区间最左（右）端是否被覆盖。

num：区间内部的端点个数。

由于这个函数大变样了，我在这里梳理一下整个函数的思路：

首先，如果这个区间被覆盖了至少一次（不管祖先，祖先的事情用不到后代关心），那么这个点的总覆盖长度就是点的总长度，这一段内部自然也不会有端点，而左右两边自然都被覆盖了。

然后是没有被覆盖且没有孩子的情况，这表明这个点和我们的覆盖区域毫无关联，因此它的覆盖长度是 0，内部没有端点，两端也都没有被覆盖。

最后是一般情况：这个点没有被覆盖，但它有孩子，有可能参与到我们的统计中来。

这一段的总覆盖长度显然就是两个孩子的长度和。

这一段内部的端点包括这样三部分：

  1. 左儿子里的
  2. 右儿子里的
  3. 两个儿子中间正好夹着一个点

这也就是处理方法。

首先，将总数设为两个儿子的数量和。

之后，如果左儿子的右边被覆盖了且右儿子的左边没有覆盖，或者左儿子的右边没有覆盖且右儿子的左边被覆盖了，那么中间就是夹着一个点。

人话：两个儿子临近对方的那一端，一个被覆盖，一个没有，那就说明中间有个端点。

如果符合上述，那么就将点数+1。

之后两端的覆盖处理和对应儿子一样，不必多言。

然后是上次的传统手艺，如果儿子没用了，就清理门户，腾出空间给其它想出生的儿孙祖先们。

下面我放一下我这次打的板子：

struct node {
    int L, R;
    node *lc, *rc;
    int cover;
    int num;
    int length;
    bool lcover, rcover;
    void pushup(void) {
        if (cover > 0) {
            length= R - L + 1;
            num= 0;
            lcover= rcover= true;
            return;
        }
        if (lc == nullptr || rc == nullptr) {
            length= 0;
            num= 0;
            lcover= rcover= false;
        } else {  // 一般
            length= lc->length + rc->length;
            num= lc->num + rc->num;
            if (lc->rcover != rc->lcover) {
                ++num;
            }
            lcover= lc->lcover;
            rcover= rc->rcover;
            if (lc->lc == rc->rc && lc->cover == 0&&rc->cover==0) {
                delete lc;
                delete rc;
                lc= rc= nullptr;
            }
        }
    }
    void add(int l, int r, int x) {
        if (l <= L && r >= R) {
            cover+= x;
            pushup();
            return;
        }
        if (lc == nullptr || rc == nullptr) {
            lc= new node;
            rc= new node;
            lc->L= L;
            lc->R= (L + R) >> 1;
            rc->L= lc->R + 1;
            rc->R= R;
            lc->cover= rc->cover= 0;
            lc->num= rc->num= 0;
            lc->lcover= lc->rcover= rc->lcover= rc->rcover= false;
            lc->length= rc->length= 0;
            lc->lc= lc->rc= rc->lc= rc->rc= nullptr;
        }
        if (l <= lc->R) lc->add(l, r, x);
        if (r >= rc->L) rc->add(l, r, x);
        pushup();
    }
};

整体和上次差不多，就是 pushup 有些变化。

然后给大家提供一下例题：P1856。

这里是这道题的主函数（这种方法）：


int main() {
    node* root= new node;
    root->L= -20000;
    root->R= 20000;
    root->num= root->cover= 0;
    root->lcover= root->rcover= false;
    root->lc= root->rc= nullptr;
    root->length= 0;
    int n;
    read(n);
    int a, b, c, d;
    for (int i= 0; i < n; ++i) {
        read(a, b, c, d);
        lines.push_back({a, {{b, d - 1}, 1}});
        lines.push_back({c, {{b, d - 1}, -1}});
    }
    sort(lines.begin(), lines.end());
    int ans= 0;
    int l1,l2;
    for (int i= 0; i < lines.size(); ++i) {
        if (i != 0) {
            ans+= root->num * (lines[i].first - lines[i - 1].first);
        }
        ans+=root->length*2;
        l1=root->length;
        root->add(lines[i].second.first.first, lines[i].second.first.second, lines[i].second.second);
        l2=root->length;
        ans-=2*min(l1,l2);
    }
    cout << ans;
}

read 是快读，可以换掉。

但是，这并不是我第一遍过的代码。

我第一遍过的代码长这样（主函数）：


int main() {
    node* root= new node;
    root->L= -20000;
    root->R= 20000;
    root->num= root->cover= 0;
    root->lcover= root->rcover= false;
    root->lc= root->rc= nullptr;
    root->length= 0;
    int n;
    read(n);
    int a, b, c, d;
    for (int i= 0; i < n; ++i) {
        read(a, b, c, d);
        lines.push_back({a, {{b, d - 1}, 1}});
        lines.push_back({c, {{b, d - 1}, -1}});
    }
    sort(lines.begin(), lines.end());
    int ans= 0;
    for (int i= 0; i < lines.size(); ++i) {
        if (i != 0) {
            ans+= root->num * (lines[i].first - lines[i - 1].first);
        };
        ans+= lines[i].second.first.second - lines[i].second.first.first + 1;
        if (lines[i].second.second > 0) {
            ans-= root->ask(lines[i].second.first.first, lines[i].second.first.second);
            root->add(lines[i].second.first.first, lines[i].second.first.second, lines[i].second.second);
        } else {
            root->add(lines[i].second.first.first, lines[i].second.first.second, lines[i].second.second);
            ans-= root->ask(lines[i].second.first.first, lines[i].second.first.second);
        }
    }
    cout << ans;
}

这是我的思路：

我们先把这次的横向宽度算出来，然后直接处理和扫描线平行的部分。

如果这次是添加了一条边，那么这部分的长度就是我们新加入的实际长度（也就是在扫描线上多出的那一块），只要用这一条边的总长度减去增加前那个区域原本就被覆盖过的长度。

如果这次是删除了一条边，那么就是我们去掉的实际长度，只要用这一条边的总长度减去删掉这条边后那一部分还没有删掉的长度。

具体看某一部分的覆盖长度使用了结构体里的 ask 函数，长这样：

int ask(int l, int r) {
    if (cover > 0) {
        return min(r, R) - max(l, L) + 1;
    }
    if (l <= L && r >= R) {
        return length;
    }
    if (lc == nullptr && rc == nullptr) return 0;
    if (r <= lc->R) return lc->ask(l, r);
    if (l >= rc->L) return rc->ask(l, r);
    return lc->ask(l, r) + rc->ask(l, r);
}

这两种方法都能通过此题，所以能记住哪种就用哪种吧。

好了，我要讲的就这么多了，如果我还有机会的话，可能会再给扫描线系列出续篇。

The End