HDU1828Picture(线段树+扫描线)(周长并)

题目链接：

给你n个矩形，让你求出总的周长。

类似面积并，面积并是扫描一次，周长并是扫描了两次，x轴一次，y轴一次。每次加起来的无非都是新加的边(flag为1)或者是新减的边(flag为-1)，即加起来的是此时的总长度(T[1].val)减去上一次扫到的总长度(last)的绝对值(T[1].val - last)。(注意用c++提交，g++会wa)

#include iostream
#include cstdio
#include cstring
#include algorithm
using namespace std;
const int MAXN = 2e4 + ;
struct data {
int l , r , h , flag;
bool operator (const data cmp) const {
return h cmp.h;
}
}x[MAXN] , y[MAXN];
struct segtree {
int l , r , val , add;
}T[MAXN ];
int f(int a) {
return (a ? a : -a);
void build(int p , int l , int r) {
int mid = (l + r) ;
T[p].l = l , T[p].r = r , T[p].add = T[p].val = ;
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(l == T[p].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 , x1 , x2 , y1 , y2;
while(~scanf("%d" , n)) {
for(int i = ; i i++) {
scanf("%d %d %d %d" , x1 , y1 , x2 , y2);
x1 += 1e4 , x2 += 1e4 , y1 += 1e4 , y2 += 1e4;
if(x1 x2)
swap(x1 , x2);
if(y1 y2)
swap(y1 , y2);
int ls = i , rs = (i )|;
x[ls].l = x1 , x[ls].r = x2 , x[ls].h = y1 , x[ls].flag = ;
x[rs].l = x1 , x[rs].r = x2 , x[rs].h = y2 , x[rs].flag = -;
y[ls].l = y1 , y[ls].r = y2 , y[ls].h = x1 , y[ls].flag = ;
y[rs].l = y1 , y[rs].r = y2 , y[rs].h = x2 , y[rs].flag = -;
}
sort(x , x + n * );
sort(y , y + n * );
build( , , 2e4);
int res = , last = ;
for(int i = ; i * n ; i++) {
updata( , x[i].l , x[i].r , x[i].flag);
res += f(last - T[].val);
last = T[].val;
}
for(int i = ; i * n ; i++) {
updata( , y[i].l , y[i].r , y[i].flag);
res += f(last - T[].val);
last = T[].val;
}
printf("%d\n" , res);
}
}