HDU 1828 Picture (线段树+扫描线)(周长并)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1828

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

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

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 const int MAXN = 2e4 + 10;
 7 struct data {
 8     int l , r , h , flag;
 9     bool operator <(const data& cmp) const {
10         return h < cmp.h;
11     }
12 }x[MAXN] , y[MAXN];
13 struct segtree {
14     int l , r , val , add;
15 }T[MAXN << 2];
16 
17 int f(int a) {
18     return (a > 0 ? a : -a);
19 }
20 
21 void build(int p , int l , int r) {
22     int mid = (l + r) >> 1;
23     T[p].l = l , T[p].r = r , T[p].add = T[p].val = 0;
24     if(r - l == 1) {
25         return ;
26     }
27     build(p << 1 , l , mid);
28     build((p << 1)|1 , mid , r);
29 }
30 
31 void pushup(int p) {
32     if(T[p].add) {
33         T[p].val = T[p].r - T[p].l;
34     }
35     else if(T[p].r - T[p].l == 1) {
36         T[p].val = 0;
37     }
38     else {
39         T[p].val = T[p << 1].val + T[(p << 1)|1].val;
40     }
41 }
42 
43 void updata(int p , int l , int r , int add) {
44     int mid = (T[p].l + T[p].r) >> 1;
45     if(l == T[p].l && T[p].r == r) {
46         T[p].add += add;
47         pushup(p);
48         return ;
49     }
50     if(r <= mid) {
51         updata(p << 1 , l , r , add);
52     }
53     else if(l >= mid) {
54         updata((p << 1)|1 , l , r , add);
55     }
56     else {
57         updata(p << 1 , l , mid , add);
58         updata((p << 1)|1 , mid , r , add);
59     }
60     pushup(p);
61 }
62 
63 int main()
64 {
65     int n , x1 , x2 , y1 , y2;
66     while(~scanf("%d" , &n)) {
67         for(int i = 0 ; i < n ; i++) {
68             scanf("%d %d %d %d" , &x1 , &y1 , &x2 , &y2);
69             x1 += 1e4 , x2 += 1e4 , y1 += 1e4 , y2 += 1e4;
70             if(x1 > x2)
71                 swap(x1 , x2);
72             if(y1 > y2)
73                 swap(y1 , y2);
74             int ls = i<<1 , rs = (i<<1)|1;
75             x[ls].l = x1 , x[ls].r = x2 , x[ls].h = y1 , x[ls].flag = 1;
76             x[rs].l = x1 , x[rs].r = x2 , x[rs].h = y2 , x[rs].flag = -1;
77             y[ls].l = y1 , y[ls].r = y2 , y[ls].h = x1 , y[ls].flag = 1;
78             y[rs].l = y1 , y[rs].r = y2 , y[rs].h = x2 , y[rs].flag = -1;
79         }
80         sort(x , x + n * 2);
81         sort(y , y + n * 2);
82         build(1 , 0 , 2e4);
83         int res = 0 , last = 0;
84         for(int i = 0 ; i < 2 * n ; i++) {
85             updata(1 , x[i].l , x[i].r , x[i].flag);
86             res += f(last - T[1].val);
87             last = T[1].val;
88         }
89         for(int i = 0 ; i < 2 * n ; i++) {
90             updata(1 , y[i].l , y[i].r , y[i].flag);
91             res += f(last - T[1].val);
92             last = T[1].val;
93         }
94         printf("%d
" , res);
95     }
96 }