poj2528Mayor's posters

题目链接：http://poj.org/problem?id=2528

区间覆盖。

离散化（有点特殊的离散化）。

 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 
 8 const int maxn=11111;
 9 int cnt;
10 int f[maxn<<4];
11 int li[maxn],ri[maxn];
12 int has[maxn],X[maxn<<3];
13 
14 void pushdown(int rt)
15 {
16     if(f[rt]!=-1)
17     {
18         f[rt<<1]=f[rt<<1|1]=f[rt];
19         f[rt]=-1;
20     }
21 }
22 
23 void update(int L,int R,int c,int l,int r,int rt)
24 {
25     if(L<=l&&r<=R)
26     {
27         f[rt]=c;
28         return ;
29     }
30     int m=(l+r)>>1;
31     pushdown(rt);
32     if(L<=m) update(L,R,c,lson);
33     if(m<R) update(L,R,c,rson);
34 }
35 void query(int l,int r,int rt)
36 {
37     if(f[rt]!=-1)
38     {
39         if(!has[f[rt]]) cnt++;
40         has[f[rt]]=1;
41         return;
42     }
43     if(l==r) return;
44     int m=(l+r)>>1;
45     query(lson);
46     query(rson);
47 }
48 int bin(int x,int n,int X[])
49 {
50     int l=0,r=n-1;
51     while(l<=r){
52     int m=(l+r)>>1;
53     if(X[m]==x) return m;
54     if(X[m]>x) r=m-1;
55     else l=m+1;
56     }
57     return -1;
58 }
59 int main()
60 {
61     int t;
62     scanf("%d",&t);
63     while(t--)
64     {
65         int n;
66         scanf("%d",&n);
67         int nn=0;
68         for(int i=0;i<n;i++){
69             scanf("%d%d",&li[i],&ri[i]);
70             X[nn++]=li[i];
71             X[nn++]=ri[i];
72         }
73         sort(X,X+nn);
74         int m=1;
75         for(int i=1;i<nn;i++)
76         {
77             if(X[i]!=X[i-1]) X[m++]=X[i];
78         }
79         for(int i=m-1;i>0;i--)
80         {
81             if(X[i]!=X[i-1]+1) X[m++]=X[i-1]+1;
82         }
83         sort(X,X+m);
84         memset(f,-1,sizeof(f));
85         for(int i=0;i<n;i++)
86         {
87             int L=bin(li[i],m,X);
88             int R=bin(ri[i],m,X);
89             update(L,R,i,0,m,1);
90         }
91         memset(has,0,sizeof(has));
92         cnt=0;
93         query(0,m,1);
94         printf("%d
",cnt);
95     }
96     return 0;
97 }
不好

很久之前做的一道题，一直有些地方很纠结。。。

今天在hiho上看到了，用上面那种离散化竟然错了。。。

学习了新姿势。。。

想起来之前在哪看的一句话，人家三天就能学到线段树的精髓，你几个月还学得稀里糊涂。。大概说的就是我了。。。

题目链接：hiho1079

在线段树的通常用法中，线段树的节点是有2种不同的意义的，一种是离散型的，比如在Hiho一下 第二十周中，一个节点虽然描述的是一个区间[3, 9]，但是实际上这样一个区间是{3, 4, 5, 6, 7, 8, 9}这样的意义。而另一种就是连续型的，比如就在这一周的问题中，一个节点如果描述的是一个区间[3, 9]，它就确确实实描述的是在数轴上从3这个标记到9这个标记的这一段。

这两种不同的意义有什么区别呢？

在小Hi看来，其实只有这样的几个区别：1.叶子节点：在离散型中，叶子节点是[i, i]，而连续性中是[i, i + 1]；2.分解区间：在离散型中，一段区间是分解成为[l, m], [m + 1, r]，而在连续型中，是分解成为[l, m], [m, r]；3.其他所有类似的判定问题。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 const int maxn=100010;
 7 int f[maxn<<4];
 8 #define lson l,m,rt<<1
 9 #define rson m,r,rt<<1|1
10 int li[maxn],ri[maxn];
11 int X[maxn<<3];
12 int has[maxn];
13 int n,lo;
14 int ct=0;
15 int ans=0;
16 
17 
18 void pushdown(int rt)
19 {
20     if(f[rt]!=-1)
21     {
22         f[rt<<1|1]=f[rt<<1]=f[rt];
23         f[rt]=-1;
24     }
25 }
26 
27 void update(int L,int R,int id,int l,int r,int rt)
28 {
29     if(L<=l&&r<=R)
30     {
31         f[rt]=id;
32         return;
33     }
34     int m=(l+r)>>1;
35     pushdown(rt);
36     if(L<m) update(L,R,id,lson);  //连续
37     if(R>m) update(L,R,id,rson);
38 }
39 void query(int l,int r,int rt)
40 {
41     if(f[rt]!=-1)
42     {
43         if(!has[f[rt]]) ans++;
44         has[f[rt]]=1;
45         return;
46     }
47     if(l+1==r) return;  //连续区间的返回条件
48     int m=(l+r)>>1;
49     query(lson);
50     query(rson);
51 }
52 
53 int Bin(int x,int len,int *X)
54 {
55     int l=0,r=len;
56     while(l<=r)
57     {
58         int m=(l+r)>>1;
59         if(X[m]==x) return m;
60         if(X[m]>x) r=m-1;
61         else l=m+1;
62     }
63     return -1;
64 }
65 int main()
66 {
67     scanf("%d%d",&n,&lo);
68     for(int i=0;i<n;i++)
69     {
70         scanf("%d%d",&li[i],&ri[i]);
71         X[ct++]=li[i];
72         X[ct++]=ri[i];
73     }
74     sort(X,X+ct);
75     int m=1;
76     for(int i=1;i<ct;i++) if(X[i]!=X[i-1]) X[m++]=X[i];  //离散化
77     m--;
78     memset(f,-1,sizeof(f));
79     for(int i=0;i<n;i++)
80     {
81         int L=Bin(li[i],m,X);
82         int R=Bin(ri[i],m,X);
83         update(L,R,i,0,m,1);
84     }
85     memset(has,0,sizeof(has));
86     query(0,m,1);
87     printf("%d
",ans);
88 }
参考

 再次更新。。。

是读题读错了ozr，题目说的线段并不是线段，它是用一个编号表示一个线段，所以本质上当成点做就可以了。。。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 const int maxn=100010;
 7 int f[maxn<<4];
 8 #define lson l,m,rt<<1
 9 #define rson m+1,r,rt<<1|1
10 int li[maxn],ri[maxn];
11 int X[maxn<<3];
12 int has[maxn];
13 int n,lo;
14 int ct=0;
15 int ans=0;
16 
17 
18 void pushdown(int rt)
19 {
20     if(f[rt]!=-1)
21     {
22         f[rt<<1|1]=f[rt<<1]=f[rt];
23         f[rt]=-1;
24     }
25 }
26 
27 void update(int L,int R,int id,int l,int r,int rt)
28 {
29     if(L<=l&&r<=R)
30     {
31         f[rt]=id;
32         return;
33     }
34     int m=(l+r)>>1;
35     pushdown(rt);
36     if(L<=m) update(L,R,id,lson);  //连续
37     if(R>m) update(L,R,id,rson);
38 }
39 void query(int l,int r,int rt)
40 {
41     if(f[rt]!=-1)
42     {
43         if(!has[f[rt]]) ans++;
44         has[f[rt]]=1;
45         return;
46     }
47     if(l==r) return;  //连续区间的返回条件
48     int m=(l+r)>>1;
49     query(lson);
50     query(rson);
51 }
52 
53 int Bin(int x,int len,int *X)
54 {
55     int l=0,r=len;
56     while(l<=r)
57     {
58         int m=(l+r)>>1;
59         if(X[m]==x) return m;
60         if(X[m]>x) r=m-1;
61         else l=m+1;
62     }
63     return -1;
64 }
65 int main()
66 {
67     int t;
68     scanf("%d",&t);
69     while(t--){
70     scanf("%d",&n);
71     for(int i=0;i<n;i++)
72     {
73         scanf("%d%d",&li[i],&ri[i]);
74         X[ct++]=li[i];
75         X[ct++]=ri[i];
76     }
77     sort(X,X+ct);
78     int m=1;
79     for(int i=1;i<ct;i++) if(X[i]!=X[i-1]) X[m++]=X[i];  //离散化
80     m--;
81     memset(f,-1,sizeof(f));
82     for(int i=0;i<n;i++)
83     {
84         int L=Bin(li[i],m,X);
85         int R=Bin(ri[i],m,X);
86         update(L,R,i,0,m,1);
87     }
88     memset(has,0,sizeof(has));
89     ans=0;
90     query(0,m,1);
91     printf("%d
",ans);
92     }
93 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/yijiull/p/6619154.html