今年省选有道题是圆面积的异或并，是扫描线的经典问题。徐人权的大纲上有太多东西我都不会，我恰好又翻到了扫描线，于是决定研究一下扫描线。
目前为止我只做了一道扫描线的题，是POJ 1177，也是IOI 98的试题，Picture，学习的还不深，在此记录一些心得。

先将平面上的元素按照一个固定的方向进行切割，把他们变成一个个按照这个方向排列的插入事件和删除事件，接着按照这个方向逐个处理事件并使用某种数据结构对当前信息进行维护，通过当前信息累计，最终求得答案。

Picture这道题的关键点倒不在于如何分割这些矩形，而是在于如何维护当前信息。
就像许多网上能够查到的该题的AC代码一样，我使用了线段树来维护信息。
不过AC代码中存在一个令我感到困惑的地方：

  • 线段树涉及到了区间快速操作，却没有tag，虽然有一个cnt域，根据这个域的定义，一个节点的祖先的cnt域不应大于该节点的cnt域，但是这个cnt域既不会上推，也不会下传，显然不能满足定义。

根据我的胡乱猜测，没有tag是因为我们的查询仅仅涉及整个区间，更小的区间的cnt域正确与否对我们所需要的结果产生不了影响。除此之外，在对一个区间进行减操作之前，之前一定会对其进行至少一个加操作，使得cnt域不会出现负数。

根据脑洞，这道题至少可以用三种不同的方法进行解答。
是由子方法A、B组合出来的。子方法A、B在我的提交代码中均有体现，实际上，我用的是AB组合
陈宏的论文
下面贴上代码及提交截图
1.png

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lson(x) (x << 1)
#define rson(x) (x << 1 | 1)
#define mid(l, r) ((l + r) >> 1)
#define MXN 10007
using namespace std;
struct seg {
    int x1, x2, y, atag;
    seg() {x1 = x2 = y = atag = 0;}
    seg(int a, int b, int c, int d):x1(a),x2(b),y(c),atag(d) {}
    bool operator<(const seg &b) const {
        return y == b.y ? atag > b.atag : y < b.y;
    }
} ss[MXN];
int cnt[20000 << 2 | 7], lne[20000 << 2 | 7];
bool lbd[20000 << 2 | 7], rbd[20000 << 2 | 7];
int stree[20000 << 2 | 7];
inline void pushup(int root, int l, int r) {
    if (cnt[root]) {
        lbd[root] = rbd[root] = true;
        stree[root] = r - l + 1;
        lne[root] = 1;
    } else if (l == r) {
        lbd[root] = rbd[root] = false;
        lne[root] = stree[root] = 0;
    } else {
        stree[root] = stree[lson(root)] + stree[rson(root)];
        lne[root] = lne[lson(root)] + lne[rson(root)];
        if (rbd[lson(root)] && lbd[rson(root)]) --lne[root];
        lbd[root] = lbd[lson(root)];
        rbd[root] = rbd[rson(root)];
    }
}
void adddata(int root, int l, int r, int al, int ar, int data) {
    if (l > ar || r < al) return;
    if (l >= al && r <= ar) {
        cnt[root] += data;
        pushup(root, l, r);
        return;
    }
    adddata(lson(root), l, mid(l, r), al, ar, data);
    adddata(rson(root), mid(l, r) + 1, r, al, ar, data);
    pushup(root, l, r);
}

int main() {
    int n;
    while (~scanf("%d", &n)) {
        int a, b, c, d;
        int m = 0;
        int lbd = 999999, rbd = -999999;
        for (int i = 0; i < n; ++i) {
            scanf("%d %d %d %d", &a, &b, &c, &d);
            lbd = std::min(lbd, a);
            rbd = std::max(rbd, c);
            ss[m++] = seg(a, c, b, 1);
            ss[m++] = seg(a, c, d, -1);
        }
        sort(ss, ss + m);
        int last = 0, resu = 0;
        for (int i = 0; i < m; ++i) {
            adddata(1, lbd, rbd - 1, ss[i].x1, ss[i].x2 - 1, ss[i].atag);
            if (i != m - 1) resu += (lne[1] << 1) * (ss[i + 1].y - ss[i].y);
            resu += std::abs(stree[1] - last);
            last = stree[1];
        }
        printf("%d\n", resu);
    }
}