矩形周长

 

https://www.luogu.com.cn/problem/P1856

题意

给出许多矩形,给出的数据为左下角和右上角,求解这些矩形并的周长。

思路

同求解矩形的面积一样,我们采取扫描线的手段来获取当前的线段长度。

一个线段一定为产生两个端点。因此我们同样也需要求解出段数,对于一个线段树来说,我们的段数还算很好维护的。

我们一个线段我们需要维护一些信息 L , R , len , cnt , block

其中 L 表示这个线段的左端点我们取得到,R 同理。 len 表示线段的长度。 cnt 表示线段被加入的次数 , block。表示线段的段数

alt

对于这样的节点,得到以下结论是显然的

  • L[p] = L(Lson(p))
  • R[p] = R(Rson(p))
  • len[p] = len[Lson(p)] + len[Rson(p)]

那么我们的 block 如果中间两个端点都有,说明中间是相连的,否则不相连。因此我我们也可以轻易的得出这样的结论

  • block[p] = block[Lson(p)] + block[Rson(p)] - L[Rson(p)] && R[Lson(p)]

扫描线计算的时间了。

我们可以采取两种做法。

方法一

假定,我们是从左到右进行扫描线。

我们可以记录上一个点last,当前的点减去上一个点就是距离,然后我们每次都求出来他们线段的个数 * 2,将其乘上距离,就是我们的横向线段的长度。

然后我们再次从下到上扫描以下就可以得到答案。

值得注意的是,如果采取这种方法的话,我并不需要维护线段树中的线段长度,因为在从左到右扫描的时候,我们的竖直方向的线段并没有参与运算。

方法二

假定,我们是从左到右进行扫描线。

首先,横向的线段我们同上面的方法相同。

那么剩下来处理竖向即可。

我们记录两个信息,last_len一个是上一个线段的的长度,另一个__add是上一个点是加边还是减边。

alt

对于初始步骤,我们先将 last_len 初始化为 0last 初始化为 -inf

然后我们随着 x 的大小来遍历整个矩形。

首先达到位置 1 ,检测到 x != last。我们计算线段树中的值。求得 now_len = 0 。我们的竖向长度增加 |now_len - last_len| 也就是 0,然后再我们将 1 号边加入,赋值last = x , last_len = now_len

然后我们来到 2 号边,检测到 x != last。我们计算出,now_len 是一号边的长度,那么我们竖向边的长度加上 |now_len - last_len| 也就是 1 号边的长度,赋值,加边。

随后,我们到达下一个边 3 号边了,检测到 x != last。计算得出,now_len 也就是上图中 now_len 的长度。那么我们这两个边的差值 |now_len - last_len| = real_add_len。就是我们所增加的值,重复上述操作,赋值,加边。 alt

如此往复直到最后,我们其实还剩下一个边,就是最右边的边没有加入我们的答案中,那么此时的 last_len 就是我们要加的边,此时,我们只需要ans += last_len 就可以更新答案了。

到这里,是不是发现我们上面有一个东西其实没有用上,我们想想 __add 为什么要存在呢?明明到这里已经完整的得到了上一个边和现在边的差值,就是我们想要的东西啊。

如果不加上接下来的步骤,你将痛失最后一个测试点 AC 的机会。

考虑这样一组测试数据

alt

由于我们并没有做出任何特殊处理,当我们到达 2 号节点的时候,我们将会有可能出现如下的错误。

当我们计算到 3 号节点的时候,我们的 now_len 是线段在 2 号节点的长度。而 last_len 却是线段在 1 号节点的长度。

那么,显然 |now_len - last_len| 并不能得到正确的长度。

如果我们想要得到正确的长度的话,我们可以进行如下的改进。将遍历顺序改为,以 x 为主关键字,是否减边为副关键字(加边在前)。

如果按照这种方式进行改进的时候,我们到达 2 号节点进行第一个删边的时候,我们得到的 now_len 就入下图所示。

alt

那么此时,我们就完美求出我们新加的俩个小边的值 |now_len - last_len|。随后执行删边。

那么我到达三号节点的时候,计算得到的 last_lennow_len 就如下图所示。

alt

那么到此,我们的操做就完全结束了。

事实上,如果我们记录 last 的值为上一个 len 我们也可以完成这个题目,具体大致相同,不过上一个 x 的位置还是省不了的。

详见注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>
using namespace std;

using PII = pair<int, int>;
using LL = long long;

const int N = 50000 + 10;
long long leng[N * 2];

struct SEG_Tree {
    vector<PII> Range;
    vector<LL> value;
    vector<int> cnt;
    vector<int> tie;
    vector<bool> Le, Ri;
    SEG_Tree(int n) {
        int size = 1;
        while (size < n) size *= 2;
        Range = vector<PII>(size * 2);
        value = vector<LL>(size * 2);
        tie = cnt = vector<int>(size * 2);
        Le = Ri = vector<bool>(size * 2);
        build(0, n);
    }

    int Lson(int x) { return x * 2 + 1; }
    int Rson(int x) { return x * 2 + 2; }

    long long len(int p) {
        return leng[Range[p].second + 1] - leng[Range[p].first];
    }

    void push_up(int p) {
        int L = Lson(p), R = Rson(p);
        if (cnt[p]) {
            value[p] = len(p);
            Le[p] = Ri[p] = true;
            tie[p] = 1;
        } else {
            value[p] = value[L] + value[R];
            Le[p] = Le[L], Ri[p] = Ri[R];
            tie[p] = tie[L] + tie[R];
            if (Ri[L] && Le[R]) tie[p]--;
        }
    }

    void build(int l, int r, int p = 0) {
        Range[p] = {l, r};
        if (l == r) {
            Le[p] = Ri[p] = false;
            cnt[p] = tie[p] = value[p] = 0;
            return;
        }
        int m = (l + r) >> 1;
        build(l, m, Lson(p));
        build(m + 1, r, Rson(p));
        push_up(p);
    }

    void add(int x, int y, int v, int p = 0) {
        auto [l, r] = Range[p];
        if (l == r) {
            cnt[p] += v;
            if (cnt[p]) {
                value[p] = len(p);
                Le[p] = Ri[p] = true;
                tie[p] = 1;
            } else {
                value[p] = 0;
                Le[p] = Ri[p] = false;
                tie[p] = 0;
            }
            return;
        }
        if (x <= l && r <= y) {
            cnt[p] += v;
            push_up(p);
            return;
        }

        int m = (l + r) >> 1;
        if (x <= m) add(x, y, v, Lson(p));
        if (y > m) add(x, y, v, Rson(p));
        push_up(p);
    }

    int se() { return tie[0]; }
    int le() { return value[0]; }
};

int main() {
    int n;
    cin >> n;
    vector<tuple<int, int, int, int>> v(n * 2);

    for (int i = 0; i < n; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        v[i * 2] = {x1, 1, y1, y2};
        v[i * 2 + 1] = {x2, -1, y1, y2};
        leng[i * 2] = y1;
        leng[i * 2 + 1] = y2;
    }
    sort(v.begin(), v.end(), [](auto x, auto y) {
        auto [x1, v, y1, y2] = x;
        auto [xx1, vv, yy1, yy2] = y;
        if (x1 == xx1) return v > vv;
        return x1 < xx1;
    });
    n *= 2;
    sort(leng, leng + n);
    n = unique(leng, leng + n) - leng;

    SEG_Tree st(n);

    auto find = [&](int x) { return lower_bound(leng, leng + n, x) - leng; };

    int last = -1001011;
    long long ans = 0;
    long long len = 0;
    int lsv = 0;

    for (auto [x, v, y1, y2] : v) {
        y1 = find(y1), y2 = find(y2);
        if (x != last || v != lsv) {
      // if (st.se() != len || v != lsv) {
     ///< 每次比较线段长度
            ans += st.se() * 2ll * (x - last);
            ans += abs(st.le() - len);
            last = x;
            lsv = v;
            len = st.le();
        }
        st.add(y1, y2 - 1, v);
    }
    ans += len;
    cout << ans << '\n';
}
algorithm