扫描线

“你长大后想成为什么样的人？”

“善良的人。” 男孩说。

重点

把一个矩阵分成横竖两种边界，线性扫描一种边界，另一种边界转换成区间和或差等信息，用前缀和或者线段树维护区间信息。

矩形面积并

题目： https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/4/DSL_4_A

思路：扫描线从左往右扫描，遇到左边界时，对应的区间 +1 ，遇到右边界时，对应的区间 -1 。用线段树维护区间加减情况，并统计在该区间里非 0 的位置个数。线段树，用 sum 维护非 0 位置的个数，tag 维护该区间的和。

注意点：因为要维护的区间是从 -1e9 到 1e9 ，区间比较大需要动态开点。因为这道题有一个比较特殊的性质，就是每一个左边界一定有一个对应的右边界，所以只要区间的 tag 不为 0（即大于 0 ），那 sum 就是区间长度，否则就是左右儿子的和。每次答案的增量就是，整个区间的 sum 即 c[1].sum 乘上横轴移动的距离。

细节：需要把线段树维护的整个区间右移到 1 到 2e9+1 ，不然计算 mid 的时候可能会出现问题，同时在计算 mid 的时候需要用 unsigned

#define N 10000007
int totnode, root;
struct node {int ls, rs, sum, tag;} c[N];

void pushup (int rt, int l, int r) {
    if (c[rt].tag) c[rt].sum = r - l + 1;
    else c[rt].sum = c[c[rt].ls].sum + c[c[rt].rs].sum;
}

void update(int &rt, int l, int r, int L, int R, int val) {
    if (!rt) rt = ++totnode;
    if (L <= l && r <= R) {
        c[rt].tag += val; pushup(rt, l, r);
        return;
    }
    int mid = ((unsigned)l + (unsigned)r) >> 1;
    if (L <= mid) update(c[rt].ls, l, mid, L, R, val);
    if (R > mid) update(c[rt].rs, mid + 1, r, L, R, val);
    pushup(rt, l, r);
}

struct query {int x, l, r, f;};
vector<query> q;

inline bool cmp (query a, query b) {return a.x < b.x;}

int main() {
    int n = rd();
    for (int i = 1; i <= n; ++i) {
        int x1 = rd(), y1 = rd(), x2 = rd(), y2 = rd();
        q.push_back(query{x1, y1 + 1000000001, y2 + 1000000000, 1});
        q.push_back(query{x2, y1 + 1000000001, y2 + 1000000000, -1});
    }
    sort(q.begin(), q.end(), cmp);
    ll ans = 0; int lst = q[0].x;
    for (int i = 0; i < (int)q.size();) {
        int x = q[i].x; ans += 1ll * c[1].sum * (x - lst);
        while (i < (int)q.size() && q[i].x == x) {
            update(root, 1, 2e9 + 1, q[i].l, q[i].r, q[i].f);
            ++i;
        }
        lst = x;
    }
    printf("%lld\n", ans);
    return 0;
}

数矩形内有多少个点