CFGYM101982F (2018 ICPC Pacific Northwest Regional Contest – Rectangles)

题意：给定n(1e5)个矩形，边与坐标轴平行，四个点的坐标都是整数(1e9级别)，问被矩形覆盖了奇数次的面积和。

首先把所有的矩形拆成上边和下边两条边，这样我们就得到了若干条与x轴平行的线段。然后我们把这些线段按照y坐标从小到大排个序。

现在我们维护一棵线段树，下标表示的是（离散化后的）整个横轴的覆盖情况。以及为了方便起见，整个线段树上所表示的区间都是左闭右开的（一条线段所能表示的实际长度是右端点减左端点）。

现在我们按照y坐标从小到大枚举每一条横线，对于一条横线，我们把它在线段树上所覆盖的的区域异或上1，同时面积取反（即用线段长度减掉区域内被标记过的线段长度和，此操作即为异或），由于我们存储的都是左闭右开区间，所以直接用右端点对应的数减掉左端点对应的数即可。

最后每插入一条线段，我们就查一下现在线段树上被覆盖的区间长度，然后乘上下一条线段的高度减掉当前线段的高度（此方法是可以正常处理有相同高度的线段的，因为他们高度相同，所以算出来都是0）。

#include <algorithm>
#include <iostream>
#include <vector>

using int_t = long long int;

using std::cin;
using std::cout;
using std::endl;

struct Segment {
    int_t left, right, height;
};
struct Node {
    Node *left = nullptr, *right = nullptr;
    int_t begin, end;
    bool flag = false;
    int_t sum = 0;
    const std::vector<int_t>& vals;
    Node(int_t begin, int_t end, const std::vector<int_t>& vals)
        : begin(begin), end(end), vals(vals) {}
    void swap() {
        flag ^= 1;
        sum = vals[end] - vals[begin] - sum;
    }
    void pushdown() {
        if (flag) {
            left->swap();
            right->swap();
            flag = 0;
        }
    }
    void maintain() { sum = left->sum + right->sum; }
    void insert(int_t begin, int_t end) {  //插入一条线段
#ifdef DEBUG
        cout << "insert " << begin << "," << end << " to " << this->begin << ","
             << this->end << endl;
#endif
        if (this->begin >= begin && this->end <= end) {
            this->swap();
            return;
        }
        if (this->begin >= end || this->end <= begin) {
            return;
        }
        int_t mid0 = (this->begin + this->end) / 2;
        pushdown();
        left->insert(begin, end);
        right->insert(begin, end);
        maintain();
    }
};
Node* build(int_t begin, int_t end, const std::vector<int_t>& vals) {
    Node* node = new Node(begin, end, vals);
    if (begin + 1 != end) {
        int_t mid = (begin + end) / 2;
        node->left = build(begin, mid, vals);
        node->right = build(mid, end, vals);
    }
    return node;
}
int main() {
    std::ios::sync_with_stdio(false);
    std::vector<Segment> segs;
    std::vector<int_t> nums;
    int_t n;
    cin >> n;
    for (int_t i = 1; i <= n; i++) {
        int_t x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        segs.push_back(Segment{x1, x2, y1});
        segs.push_back(Segment{x1, x2, y2});
        nums.push_back(x1);
        nums.push_back(x2);
    }
    std::sort(nums.begin(), nums.end());
    nums.resize(std::unique(nums.begin(), nums.end()) - nums.begin());

    std::sort(segs.begin(), segs.end(), [](const Segment& a, const Segment& b) {
        return a.height < b.height;
    });
    int_t result = 0;
    Node* root = build(0, nums.size() - 1, nums);
    const auto rank = [&](int_t x) {
        return std::lower_bound(nums.begin(), nums.end(), x) - nums.begin();
    };
#ifdef DEBUG
    for (const auto& s : segs) {
        cout << "seg " << s.left << " " << s.right << " " << s.height << endl;
    }
#endif
    for (int_t i = 0; i < segs.size() - 1; i++) {
        //先插入后统计结果
        const auto& curr = segs[i];
        root->insert(rank(curr.left), rank(curr.right));
        result += (segs[i + 1].height - curr.height) * root->sum;
    }
    cout << result << endl;
    return 0;
}