题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3265
给你n个中间被挖空了一个矩形的中空矩形，让你求他们的面积并。
其实一个中空矩形可以分成4个小的矩形，然后就是面积并，特别注意的是x1 == x3 || x2 == x4的时候，要特判一下，否则会RE。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 2e5 + ;
typedef long long LL;
struct data {
LL l , r , y , flag;
bool operator <(const data& cmp) const {
return y < cmp.y;
}
}a[MAXN << ];
struct segtree {
LL val , l , r , add;
}T[MAXN << ]; void build(int p , int l , int r) {
int mid = (l + r) >> ;
T[p].l = l , T[p].r = r , T[p].val = T[p].add = ;
if(r - l == ) {
return ;
}
build(p << , l , mid);
build((p << )| , mid , r);
} void pushup(int p) {
if(T[p].add) {
T[p].val = T[p].r - T[p].l;
}
else if(T[p].r - T[p].l == ){
T[p].val = ;
}
else {
T[p].val = T[p << ].val + T[(p << )|].val;
}
} void updata(int p , int l , int r , int add) {
int mid = (T[p].l + T[p].r) >> ;
if(T[p].l == l && T[p].r == r) {
T[p].add += add;
pushup(p);
return ;
}
if(r <= mid) {
updata(p << , l , r , add);
}
else if(l >= mid) {
updata((p << )| , l , r , add);
}
else {
updata(p << , l , mid , add);
updata((p << )| , mid , r , add);
}
pushup(p);
} int main()
{
int n;
LL x[] , y[];
while(~scanf("%d" , &n) && n) {
int f = ;
for(int i = ; i < n ; i++) {
for(int j = ; j <= ; j++) {
scanf("%lld %lld" , x + j , y + j);
}
sort(x + , x + );
sort(y + , y + );
a[f].l = x[] , a[f].r = x[] , a[f].y = y[] , a[f].flag = -;
f++;
a[f].l = x[] , a[f].r = x[] , a[f].y = y[] , a[f].flag = ;
f++;
a[f].l = x[] , a[f].r = x[] , a[f].y = y[] , a[f].flag = -;
f++;
a[f].l = x[] , a[f].r = x[] , a[f].y = y[] , a[f].flag = ;
f++; a[f].l = x[] , a[f].r = x[] , a[f].y = y[] , a[f].flag = -;
f++;
a[f].l = x[] , a[f].r = x[] , a[f].y = y[] , a[f].flag = ;
f++;
a[f].l = x[] , a[f].r = x[] , a[f].y = y[] , a[f].flag = -;
f++;
a[f].l = x[] , a[f].r = x[] , a[f].y = y[] , a[f].flag = ;
f++;
}
sort(a , a + f);
LL res = ;
build( , , 2e5 + );
//注意l == r的特殊情况
if(a[].l != a[].r)
updata( , a[].l , a[].r , a[].flag);
for(int i = ; i < f ; i++) {
res += (a[i].y - a[i - ].y) * T[].val;
if(a[i].r > a[i].l)
updata( , a[i].l , a[i].r , a[i].flag);
}
printf("%lld\n" , res);
}
}