[HDOJ1255] 覆盖的面积（线段树，扫描线，矩形面积交）

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

题意：求矩形面积交

上信安的时候撕烤了很久如何求交，发现只需要在线段树里额外维护一个tlen，代表覆盖两次以上的长度，在pushup的时候分情况更新就行了。

一直调不出来，最后发现是pushup的时候犯傻B了：当前节点代表的线段覆盖过一次的时候，那么覆盖两次的长度应该从左右儿子的覆盖1次的线段更新上来，而不是覆盖2次的（从覆盖2次的更新上来就是覆盖三次的啦喂）。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define lrt rt << 1
 5 #define rrt rt << 1 | 1
 6 typedef struct Seg {
 7     double len, tlen;
 8     int sign;
 9 }Seg;
10 typedef struct Event {
11     double l, r, h;
12     int sign;
13 }Event;
14 const int maxn = 2100;
15 int n, hcnt;
16 vector<Event> event;
17 double h[maxn];
18 Seg seg[maxn<<2];
19 
20 bool cmp(Event a, Event b) {
21     if(a.h != b.h) return a.h < b.h;
22     return a.sign > b.sign;
23 }
24 
25 int id(double x) {
26     return lower_bound(h, h+hcnt, x) - h + 1;
27 }
28 
29 void build(int l, int r, int rt) {
30     seg[rt].len = seg[rt].tlen = .0;
31     seg[rt].sign = 0;
32     if(l == r) return;
33     int mid = (l + r) >> 1;
34     build(l, mid, lrt);
35     build(mid+1, r, rrt);
36 }
37 
38 void pushup(int l, int r, int rt) {
39     if(seg[rt].sign) {
40         seg[rt].len = h[r] - h[l-1];
41         if(seg[rt].sign > 1) seg[rt].tlen = seg[rt].len;
42         else seg[rt].tlen = seg[lrt].len + seg[rrt].len;
43     }
44     else {
45         if(l == r) seg[rt].len = seg[rt].tlen = 0;
46         else {
47             seg[rt].len = seg[lrt].len + seg[rrt].len;
48             seg[rt].tlen = seg[lrt].tlen + seg[rrt].tlen;
49         }
50     }
51 }
52 
53 void update(int L, int R, int sign, int l, int r, int rt) {
54     if(L <= l && r <= R) {
55         seg[rt].sign += sign;
56         pushup(l, r, rt);
57         return;
58     }
59     int mid = (l + r) >> 1;
60     if(L <= mid) update(L, R, sign, l, mid, lrt);
61     if(mid < R) update(L, R, sign, mid+1, r, rrt);
62     pushup(l, r, rt);
63 }
64 
65 int main() {
66     // freopen("in", "r", stdin);
67     int T;
68     double ax, ay, bx, by;
69     scanf("%d", &T);
70     while(T--) {
71         event.clear(); hcnt = 0;
72         scanf("%d", &n);
73         for(int i = 0; i < n; i++) {
74             scanf("%lf%lf%lf%lf",&ax,&ay,&bx,&by);
75             event.push_back(Event{ax,bx,ay,1});
76             event.push_back(Event{ax,bx,by,-1});
77             h[hcnt++] = ax, h[hcnt++] = bx;
78         }
79         sort(event.begin(), event.end(), cmp);
80         sort(h, h+hcnt); hcnt = unique(h, h+hcnt) - h;
81         build(1, hcnt, 1);
82         double ret = .0;
83         for(int i = 0; i < event.size(); i++) {
84             int l = id(event[i].l);
85             int r = id(event[i].r) - 1;
86             int sign = event[i].sign;
87             update(l, r, sign, 1, hcnt, 1);
88             ret += (event[i+1].h - event[i].h) * seg[1].tlen;
89         }
90         printf("%.2f
", ret);
91     }
92     return 0;
93 }