51Nod 1206. Picture[矩形并周长](扫描线+区间覆盖线段树)

日付: 10月 22, 2018

[Picture问题 - 51Nod](https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1206)

## Problem
求平面上$n$个矩形并在一起的多边形的周长(包括内部)。

数据范围：$2 \le n \le 50000, -1e6 \le x[i], y[i] \le 1e6$

## Solution
周长可以分为横线的周长和竖线的周长，可以只算竖线的周长，坐标倒转后再算一遍。

对于竖线部分可以用扫描线法。一个矩形$[(a, b), (c, d)]$，分解为两个扫描事件$(a, -1, b, d)$和$(c, 1, b, d)$，分别代表在横坐标$a$处打开以及在$c$处关闭了区间$[b, d)$(长度是整点数量减去1，所以要去掉一个端点)。注意这里打开一定要在关闭之前，否则会导致重复计算。将事件排序后遍历，就相当于从左到右的扫描过程。

遍历时维护打开的区间的覆盖范围$R$。对于一条竖线，和$R$重合的部分一定是在某个矩形内部，所以用竖线的长度减去重合的长度就可以得到对答案贡献。当遍历到打开区间时，先计算贡献然后添加区间，当遍历到关闭区间时，先删除区间然后计算贡献。因为涉及到区间的删除，只维护覆盖范围是不够的，还要维护覆盖的次数。如果有一个线段树能够同时维护区间和与区间非0值的和那么问题就很容易解决了。

遗憾的是，无法构造出这样的线段树。但是仔细观察可以发现该问题的一些性质。比如，增加和删除区间对答案的贡献等于$R$的长度变化，因此只需知道$R$整体而非区间$[b,d)$内的长度就足够了。

构造这样一个线段树，结点定义为$(cnt, sum)$，分别表示该结点的区间被完全覆盖了多少次，以及覆盖范围的长度。当$cnt>0$时，$sum$为区间长度，当$cnt=0$时，$sum$为左右儿子的$sum$和(如果是叶子结点就为0)。当更新区间$[b,d)$时，如果找到了完全包含于其中的结点，$cnt$加1或减1然后按照上述规则更新，**不需要向下传播**。不是完全包含则递归计算左右儿子然后更新当前结点。

简要分析一下正确性。
1. 每个结点上的$cnt$并不等于对应区间被完全覆盖的次数，而只包括了更新过程中对其修改的次数，比如对祖先的修改并不会传递到当前结点。对每一个结点，$cnt$一定不会小于0，因为区间是成对出现，先增后删的，这样就保证了对于$p$结点，如果$cnt>0$的情况一定是整个区间都覆盖了，因为修改其他结点不会使$p$的覆盖范围变小。
2. 每个结点的$sum$，其实只统计了其自身与子孙结点对覆盖范围的贡献。因此对于根结点，$sum$等于真正的覆盖范围。

```c++
#include <bits/stdc++.h>
using namespace std;

struct RangeCover {
    int n;
    vector<int> C, S;
    RangeCover(int n) : n(n), C(n * 2), S(n * 2) {}

void apply(int p, int v, int k) {
        C[p] += v, assert(C[p] >= 0), S[p] = C[p] ? k : p < n ? S[p << 1] + S[p << 1 | 1] : 0;
    }
    void build(int p) { for (int k = 2; p > 1; k <<= 1) p >>= 1, apply(p, 0, k); }
    void modify(int l, int r, int v) {
        assert(l < r);
        int l0 = l, r0 = r, k = 1;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1, k <<= 1) {
            if (l & 1) apply(l++, v, k);
            if (r & 1) apply(--r, v, k);
        }
        build(l0 + n), build(r0 - 1 + n);
    }
    int ans() const { return S[1]; }
};

// 51Nod. 1206
int main() {
    using LL = long long;
    int n;
    scanf("%d", &n);
    vector<array<int, 4>> A;
    const int Bias = 1e6;
    for (int i = 0; i < n; i++) {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        a += Bias, b += Bias, c += Bias, d += Bias;
        A.push_back({a, b, c, d});
    }
    auto solve = [&]() {
        vector<array<int, 4>> E;
        for (auto& t : A) {
            E.push_back({t[0], -1, t[1], t[3]});
            E.push_back({t[2], 1, t[1], t[3]});
        }
        sort(E.begin(), E.end());
        RangeCover rc(Bias * 2 + 1);
        LL ans = 0;
        for (auto& e : E) {
            int pre = rc.ans();
            rc.modify(e[2], e[3], -e[1]);
            int cur = rc.ans();
            ans += abs(cur - pre);
        }
        return ans;
    };
    LL ans = solve();
    for (auto& t : A) t = {t[1], t[0], t[3], t[2]};
    ans += solve();
    printf("%lld\n", ans);
    return 0;
}
```
</details>

KONGROOの基地

このブログを検索

51Nod 1206. Picture[矩形并周长](扫描线+区间覆盖线段树)

コメント

コメントを投稿