[hdu1828] Picture

帅哥美女们大家好！
今天本蒟蒻补一篇题解！
线段树维护扫描线求矩形周长并。
扫描线的话，跟求面积类似，这道题可以只扫一次，也可以x，y两个方向分别扫一次。
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define INF 0x3f3f3f3f
 5 #define MAXN 10010
 6 #define MAXM 20010
 7 #define MAXNODE 4*MAXN
 8 using namespace std;
 9 
10 int n,m,covered[MAXM<<2],segnum[MAXM<<2],len[MAXM<<2];
11 bool lb[MAXM<<2],rb[MAXM<<2];
12 
13 struct ln
14 {
15     int x1,x2,y,cover;
16     bool operator < (const ln& x) const
17     {
18         return y<x.y;
19     }
20 }line[MAXN];
21 
22 void add(int x1,int y1,int x2,int y2)
23 {
24     line[m].x1=x1;
25     line[m].x2=x2;
26     line[m].y=y1;
27     line[m++].cover=1;
28     line[m].x1=x1;
29     line[m].x2=x2;
30     line[m].y=y2;
31     line[m++].cover=-1;
32 }
33 
34 void pushdown(int o,int L,int R)
35 {
36     if(covered[o])
37     {
38         lb[o]=rb[o]=1;
39         len[o]=R-L;
40         segnum[o]=2;
41     }
42     else if(L+1>=R)lb[o]=rb[o]=len[o]=segnum[o]=0;
43     else
44     {
45         lb[o]=lb[o<<1];
46         rb[o]=rb[o<<1|1];
47         len[o]=len[o<<1]+len[o<<1|1];
48         segnum[o]=segnum[o<<1]+segnum[o<<1|1];
49         if(rb[o<<1]&&lb[o<<1|1]) segnum[o]-=2;
50     }
51 }
52 
53 void update(int o,int L,int R,int ql,int qr,int cover)
54 {
55     if(ql<=L&&qr>=R)
56     {
57         covered[o]+=cover;
58         pushdown(o,L,R);
59         return;
60     }
61     int mid=(L+R)>>1;
62     if(ql<mid) update(o<<1,L,mid,ql,qr,cover);
63     if(qr>mid) update(o<<1|1,mid,R,ql,qr,cover);
64     pushdown(o,L,R);
65 }
66 
67 int main()
68 {
69     while(scanf("%d",&n)!=EOF)
70     {
71         m=0;
72         int LB=INF,RB=-INF;
73         while(n--)
74         {
75             int x1,y1,x2,y2;
76             scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
77             LB=min(LB,x1);
78             RB=max(RB,x2);
79             add(x1,y1,x2,y2);
80         }
81         sort(line,line+m);
82         for(int i=0;i<(MAXM<<2);i++)
83             lb[i]=rb[i]=covered[i]=segnum[i]=len[i]=0;
84         int last=0,ans=0;
85         for(int i=0;i<m-1;i++)
86         {
87             update(1,LB,RB,line[i].x1,line[i].x2,line[i].cover);
88             ans+=segnum[1]*(line[i+1].y-line[i].y);
89             ans+=abs(len[1]-last);
90             last=len[1];
91         }
92         ans+=len[1];
93         printf("%d
",ans);
94     }
95     return 0;
96 }
hdu1828 Picture