【HDU】1828 Picture

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<algorithm>
 5 #define MAXN 20010
 6 #define INF 123456789
 7 using namespace std;
 8 struct Line
 9 {
10     int left,right,high,flag;
11 };
12 Line p[MAXN];
13 struct node
14 {
15     int sum,cnt,left,right,vertical;
16 }tree[MAXN<<2];
17 int cmp(const void *a,const void *b)
18 {
19     return (*(Line *)a).high-(*(Line *)b).high;
20 }
21 inline void PushUp(int L,int R,int rt)
22 {
23     if(tree[rt].cnt)
24     {
25         tree[rt].sum=R-L+1;
26         tree[rt].left=tree[rt].right=1;
27         tree[rt].vertical=2;
28     }
29     else if(L==R)
30         tree[rt].sum=tree[rt].left=tree[rt].right=tree[rt].vertical=0;
31     else
32     {
33         tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
34         tree[rt].left=tree[rt<<1].left;
35         tree[rt].right=tree[rt<<1|1].right;
36         tree[rt].vertical=tree[rt<<1].vertical+tree[rt<<1|1].vertical;
37         if(tree[rt<<1].right&&tree[rt<<1|1].left)
38             tree[rt].vertical-=2;
39     }
40 }
41 void Update(int x,int y,int flag,int L,int R,int rt)
42 {
43     if(x<=L&&R<=y)
44     {
45         tree[rt].cnt+=flag;
46         PushUp(L,R,rt);
47     }
48     else
49     {
50         int mid=(L+R)>>1;
51         if(mid>=x)
52             Update(x,y,flag,L,mid,rt<<1);
53         if(y>mid)
54             Update(x,y,flag,mid+1,R,rt<<1|1);
55         PushUp(L,R,rt);
56     }
57 }
58 int main()
59 {
60     int ans,i,n,x1,y1,x2,y2,left,right,cnt,last;
61     while(~scanf("%d",&n))
62     {
63         left=INF;
64         right=-INF;
65         for(i=cnt=0;i<n;i++)
66         {
67             scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
68             p[cnt].left=x1;
69             p[cnt].right=x2;
70             p[cnt].flag=1;
71             p[cnt++].high=y1;
72             p[cnt].left=x1;
73             p[cnt].right=x2;
74             p[cnt].flag=-1;
75             p[cnt++].high=y2;
76             left=min(left,x1);
77             right=max(right,x2);
78         }
79         qsort(p,cnt,sizeof(p[0]),cmp);
80         memset(tree,0,sizeof(tree));
81         for(ans=last=i=0;i<cnt;i++)
82         {
83             Update(p[i].left,p[i].right-1,p[i].flag,left,right-1,1);
84             ans+=abs(tree[1].sum-last);
85             last=tree[1].sum;
86             if(i<cnt-1)
87                 ans+=(p[i+1].high-p[i].high)*tree[1].vertical;
88         }
89         printf("%d\n",ans);
90     }
91     return 0;
92 }
新博客：www.zhixiangli.com