题意：给定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;
}