Gym - 101982F Rectangles (扫描线)

Description You are given several axis-aligned rectangles. Compute the sum of the area of the regions that are covered by an odd number of rectangles.

Input The first line of input contains a single integer $n(1\le n\le 1e5)$, representing the number of rectangles.Each of the next n lines contains four space-separated integers x1, y1, x2, and y2, each between 0 and $1e9$, describing the coordinates of a rectangle.

Output Print, on one line, the total area covered by an odd number of rectangles as an exact integer

Examples Input 2 0 0 4 4 1 1 3 3

Output 12

Input 4 0 0 10 10 1 1 11 11 2 2 12 12 3 3 13 13

Output 72

Solution 和一般的扫描线不同，这题要求被奇数个矩形覆盖的区域的面积。 我们可以利用线段树实现区间取反 每来一条扫描线就把该区间取反，并维护权值为1的区间总长度，同时统计答案

Code

// #include <bits/stdc++.h> #include <cstdio> #include <iostream> #include <vector> #include <cstring> #include <algorithm> #define ls rt << 1 #define rs rt << 1 | 1 using namespace std; typedef long long ll; const int MX = 4e5 + 7; int n,X[MX<<1]; struct Scanline{ int l,r,h; inline bool operator<(const Scanline&it) const{ return h < it.h; } }line[MX<<1]; struct SegTree{ int l,r,len,lazy; }t[MX << 3]; void build(int rt,int l,int r){ t[rt].l = l, t[rt].r = r; t[rt].lazy = t[rt].len = 0; if(l == r) return ; int mid = (l + r) >> 1; build(ls,l,mid);build(rs,mid+1,r); } void rev(int rt){ int l = t[rt].l, r = t[rt].r; int len = X[r + 1] - X[l]; t[rt].len = len - t[rt].len; } void push_down(int rt){ if(t[rt].lazy){ rev(ls);rev(rs); t[ls].lazy ^= 1;t[rs].lazy ^= 1; t[rt].lazy = 0; } } void push_up(int rt){ t[rt].len = t[ls].len + t[rs].len; } void update(int rt,int L,int R){ int l = t[rt].l, r = t[rt].r; if(R <= X[l] || L >= X[r+1]) return ; if((L <= X[l] && X[r + 1] <= R) || (l == r)){ rev(rt); t[rt].lazy ^= 1; return ; } push_down(rt); int mid = (l + r) >> 1; if(L < X[mid+1]) update(ls,L,R); if(R > X[mid+1]) update(rs,L,R); push_up(rt); } int main(){ scanf("%d",&n); for(int i = 1;i <= n;++i){ int x1,y1,x2,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2); X[i * 2 - 1] = x1, X[i * 2] = x2; line[i * 2 - 1] = (Scanline) {x1,x2,y1}; line[i * 2] = (Scanline) {x1,x2,y2}; } n <<= 1; sort(X + 1,X + 1 + n); sort(line + 1,line + 1 + n); int tot = unique(X + 1,X + 1 + n) - X - 1; build(1,1,tot - 1); ll res = 0; for(int i = 1;i < n;++i){ update(1,line[i].l,line[i].r); res += 1ll * (line[i+1].h - line[i].h) * t[1].len; } printf("%lld\n", res); }