7 -15 0 5 10 -5 8 20 25 15 -4 24 14 0 -6 16 4 2 15 10 22 30 10 36 20 34 0 40 16
228
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #define LL long long 5 using namespace std; 6 const int maxn = 100000; 7 struct node{ 8 int lt,rt,cover,len; 9 }tree[maxn<<2]; 10 struct line{ 11 int x,y,h,del; 12 line(int a = 0,int b = 0,int c = 0,int d = 0){ 13 x = a; 14 y = b; 15 h = c; 16 del = d; 17 } 18 bool operator<(const line& t)const{ 19 return h == t.h?del > t.del:h < t.h;//特别注意此处 20 } 21 }nx[maxn],ny[maxn]; 22 void build(int lt,int rt,int v){ 23 tree[v].lt = lt; 24 tree[v].rt = rt; 25 tree[v].cover = tree[v].len = 0; 26 if(lt + 1 == rt) return; 27 int mid = (lt + rt)>>1; 28 build(lt,mid,v<<1); 29 build(mid,rt,v<<1|1); 30 } 31 void modify(int v){ 32 if(tree[v].cover) tree[v].len = tree[v].rt - tree[v].lt; 33 else if(tree[v].lt + 1 == tree[v].rt) tree[v].len = 0; 34 else tree[v].len = tree[v<<1].len + tree[v<<1|1].len; 35 } 36 void update(int lt,int rt,int v,int del){ 37 if(tree[v].lt >= lt && tree[v].rt <= rt){ 38 tree[v].cover += del; 39 modify(v); 40 return; 41 } 42 int mid = (tree[v].lt + tree[v].rt)>>1; 43 if(lt < mid) update(lt,rt,v<<1,del); 44 if(rt > mid) update(lt,rt,v<<1|1,del); 45 modify(v); 46 } 47 int main(){ 48 int n,tot,x1,x2,y1,y2; 49 while(~scanf("%d",&n)){ 50 build(-20000,20000,1); 51 for(int i = tot = 0; i < n; ++i){ 52 scanf("%d %d %d %d",&x1,&y1,&x2,&y2); 53 nx[tot] = line(x1,x2,y1,1); 54 nx[tot+1] = line(x1,x2,y2,-1); 55 ny[tot] = line(y1,y2,x1,1); 56 ny[tot+1] = line(y1,y2,x2,-1); 57 tot += 2; 58 } 59 sort(nx,nx+tot); 60 sort(ny,ny+tot); 61 LL ans = 0,pre = 0; 62 for(int i = 0; i < tot; ++i){ 63 update(nx[i].x,nx[i].y,1,nx[i].del); 64 ans += abs(tree[1].len - pre); 65 pre = tree[1].len; 66 } 67 for(int i = pre = 0; i < tot; ++i){ 68 update(ny[i].x,ny[i].y,1,ny[i].del); 69 ans += abs(tree[1].len - pre); 70 pre = tree[1].len; 71 } 72 printf("%I64d\n",ans); 73 } 74 return 0; 75 }
原文：http://www.cnblogs.com/crackpotisback/p/4366992.html
