hdu1542（线段树+扫描线）

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

又看到了几个月前做的题，感觉那时候就是个sb

也怪自己刚开始没搞清楚线段树，，瞎摸索

用连续线段树很好理解这个题，之前的代码稍微改了一下就好理解多了

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define lson l,m,rt<<1
 5 #define rson m,r,rt<<1|1
 6 using namespace std;
 7 const int maxn=210;  //需要离散的x坐标数
 8 int cnt[maxn<<2];    //标记该线段是否被选
 9 double sum[maxn<<2];  //被选择的部分线段总长度
10 double X[maxn<<2];  //离散化
11 struct seg
12 {
13     double l,r;
14     double h;
15     int s;  //标记
16     seg(){}
17     seg(double l,double r,double h,int s):l(l),r(r),h(h),s(s){}
18     bool operator < (const seg &cmp) const
19     {
20         return h<cmp.h;
21     }
22 }ss[maxn];
23 
24 void pushup(int rt,int l,int r)
25 {
26     if(cnt[rt]) sum[rt]=X[r]-X[l];  //如果该线段标记被完全选择，则长度为全长。。
27     else if(l+1==r) sum[rt]=0;   //若未被完全选择，且该线段只有一段，则长度为0
28     else sum[rt]=sum[rt<<1]+sum[rt<<1|1]; //未被完全选择，且不止一段，则长度为被选择的部分
29 }
30 
31 void update(int L,int R,int c,int l,int r,int rt)
32 {
33     if(L<=l&&r<=R)
34     {
35         cnt[rt]+=c;  // 选则或者删除一次该线段
36         pushup(rt,l,r);
37         return ;
38     }
39     int m=(l+r)>>1;
40     if(L<m) update(L,R,c,lson);
41     if(m<R) update(L,R,c,rson);
42     pushup(rt,l,r);
43 }
44 int BIN(double key,int n,double X[])
45 {
46     int l=0,r=n-1;
47     while(l<=r)
48     {
49         int m=(l+r)>>1;
50         if(X[m]==key) return m;
51         if(X[m]<key) l=m+1;
52         else r=m-1;
53     }
54     return -1;
55 }
56 int main()
57 {
58     int n,cas=0;
59     while(scanf("%d",&n)&&n)
60     {
61         int m=0;
62         while(n--)
63         {
64             double a,b,c,d;
65             scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
66             X[m]=a;
67             ss[m++]=seg(a,c,b,1);
68             X[m]=c;
69             ss[m++]=seg(a,c,d,-1);
70         }
71         sort(X,X+m);
72         sort(ss,ss+m);
73         //离散化
74         int k=1;
75         for(int i=1;i<m;i++)
76             if(X[i]!=X[i-1]) X[k++]=X[i];
77 
78         memset(cnt,0,sizeof(cnt));
79         memset(sum,0,sizeof(sum));
80         double ans=0;
81         for(int i=0;i<m-1;i++)  //最上面的线段不用处理
82         {
83             int l=BIN(ss[i].l,k,X);
84             int r=BIN(ss[i].r,k,X);
85             if(l<r) update(l,r,ss[i].s,0,k-1,1);
86             ans+=sum[1]*(ss[i+1].h-ss[i].h);
87         }
88         printf("Test case #%d
Total explored area: %.2lf

",++cas,ans);
89     }
90     return 0;
91 }

View Code

下面的可以不看了。。。。。。

看了很久别人的代码才理解。。

最重要的一点是要搞清楚线段树节点的意义：节点记录的是该节点到后一个节点之间的线段长度

从0开始计数

例如：节点0-0，记录的是第0个点到第1个点之间线段的长度，即第一条线段的长度

　　　节点1-2，记录的是第1个点到第3个点之间线段的长度，即第2和第3条线段的长度

----------------------------------------------------------------------------------------

关于线段树节点的理解，不管是要维护什么信息，必须是一个点代表一个信息（类比最开始学习时维护的数组，一个下标代表一个需要维护的值）

每个节点（一个区间）中包含多个点，叶子含一个点

所以这里用线段的左端点代表这条线段，而不能用区间表示线段

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define lson l,m,rt<<1
 5 #define rson m+1,r,rt<<1|1
 6 using namespace std;
 7 const int maxn=210;  //需要离散的x坐标数
 8 int cnt[maxn<<2];    //标记该线段是否被选
 9 double sum[maxn<<2];  //被选择的部分线段总长度
10 double X[maxn<<2];  //离散化
11 struct seg
12 {
13     double l,r;
14     double h;
15     int s;  //标记
16     seg(){}
17     seg(double l,double r,double h,int s):l(l),r(r),h(h),s(s){}
18     bool operator < (const seg &cmp) const
19     {
20         return h<cmp.h;
21     }
22 }ss[maxn];  
23 
24 void pushup(int rt,int l,int r)
25 {
26     if(cnt[rt]) sum[rt]=X[r+1]-X[l];  //如果该线段标记被完全选择，则长度为全长。。注意 r+1  ！！！
27     else if(l==r) sum[rt]=0;   //若未被完全选择，且该线段只有一段，则长度为0
28     else sum[rt]=sum[rt<<1]+sum[rt<<1|1]; //未被完全选择，且不止一段，则长度为被选择的部分
29 }
30 
31 void update(int L,int R,int c,int l,int r,int rt)
32 {
33     if(L<=l&&r<=R)
34     {
35         cnt[rt]+=c;  // 选则或者删除一次该线段
36         pushup(rt,l,r);
37         return ;
38     }
39     int m=(l+r)>>1;
40     if(L<=m) update(L,R,c,lson);
41     if(m<R) update(L,R,c,rson);
42     pushup(rt,l,r);
43 }
44 int BIN(double key,int n,double X[])
45 {
46     int l=0,r=n-1;
47     while(l<=r)
48     {
49         int m=(l+r)>>1;
50         if(X[m]==key) return m;
51         if(X[m]<key) l=m+1;
52         else r=m-1;
53     }
54     return -1;
55 }
56 int main()
57 {
58     int n,cas=0;
59     while(scanf("%d",&n)&&n)
60     {
61         int m=0;
62         while(n--)
63         {
64             double a,b,c,d;
65             scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
66             X[m]=a;
67             ss[m++]=seg(a,c,b,1);
68             X[m]=c;
69             ss[m++]=seg(a,c,d,-1);
70         }
71         sort(X,X+m);
72         sort(ss,ss+m);
73         //离散化
74         int k=1;    
75         for(int i=1;i<m;i++)
76             if(X[i]!=X[i-1]) X[k++]=X[i];
77             
78         memset(cnt,0,sizeof(cnt));
79         memset(sum,0,sizeof(sum));
80         double ans=0;
81         for(int i=0;i<m-1;i++)  //最上面的线段不用处理
82         {
83             int l=BIN(ss[i].l,k,X);
84             int r=BIN(ss[i].r,k,X)-1;  //注意线段树的节点的意义！！！
85             if(l<=r) update(l,r,ss[i].s,0,k-1,1);
86             ans+=sum[1]*(ss[i+1].h-ss[i].h);
87         }
88         printf("Test case #%d
Total explored area: %.2lf

",++cas,ans);
89     }
90     return 0;
91 }