poj 2528 Mayor’s posters 【离散化】+【线段树】

题目大意：

往一堵墙上贴海报，依次输出这些海报张贴的范围，这些海报能够相互覆盖，问最后能够看见几张海报？

解题分析：

由于是给出每张海报的区间，所以在这些区间内的很多点可能用不上，所以我们采用离散化，将这个大的区间映射到一个更小更紧凑的区间。

但是只是这样简单的离散化是错误的，如三张海报为：1~10 1~4 6~10 离散化时 X[ 1 ] = 1, X[ 2 ] = 4, X[ 3 ] = 6, X[ 4 ] = 10 第一张海报时：墙的1~4被染为1；第二张海报时：墙的1~2被染为2，3~4仍为1；第三张海报时：墙的3~4被染为3，1~2仍为2。最终，第一张海报就显示被完全覆盖了，于是输出2，但实际上明显不是这样，正确输出为3。新的离散方法为：在相差大于1的数间加一个数，例如在上面1 4 6 10中间加5（算法中实际上1，4之间，6，10之间都新增了数的） X[ 1 ] = 1, X[ 2 ] = 4, X[ 3 ] = 5, X[ 4 ] = 6， X[ 5 ] = 10 这样之后，第一次是1~5被染成1；第二次1~2被染成2；第三次4~5被染成3 最终，1~2为2，3为1，4~5为3，于是输出正确结果3。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <set>
 5 using namespace std;
 6 
 7 #define Lson rt<<1,l,mid
 8 #define Rson rt<<1|1,mid+1,r
 9 const int maxn=10000+100;
10 int x[maxn<<4],tr[maxn<<4],lx[maxn<<2],rx[maxn<<2];
11 set<int>s;
12 
13 void Pushdown(int rt){
14     tr[rt<<1]=tr[rt<<1|1]=tr[rt];
15     tr[rt]=-1;
16 }
17 
18 void update(int rt,int l,int r,int L,int R,int c){
19     if(L<=l&&r<=R){
20         tr[rt]=c;
21         return;
22     }
23     if(tr[rt]!=-1)Pushdown(rt);  //如果tr[rt]==-1,说明不需要将该点的值Pushdown
24     int mid=(l+r)>>1;
25     if(L<=mid)update(Lson,L,R,c);
26     if(R>mid)update(Rson,L,R,c);
27 }
28 
29 void query(int rt,int l,int r){
30     if(tr[rt]!=-1){    //因为update的时候，只要该节点的区间包含在要求修改的区间内，就直接将值赋给该节点了，不会继续向下更新，所以，不用一直查询到子节点
31         s.insert(tr[rt]);    //用set来去掉重复的标号
32         return;
33     }
34     if(l==r)return;
35     if(tr[rt]!=-1)Pushdown(rt);
36     int mid=(l+r)>>1;
37     query(Lson);
38     query(Rson);
39 }
40 
41 int main(){
42     int T;scanf("%d",&T);
43     while(T--){
44         memset(tr,-1,sizeof(tr));
45         int cnt=0;
46         int n;scanf("%d",&n);
47         s.clear();
48         for(int i=1;i<=n;i++){
49             scanf("%d%d",&lx[i],&rx[i]);
50             x[++cnt]=lx[i];
51             x[++cnt]=rx[i];
52         }
53         sort(x+1,x+1+cnt);
54         int num=1;
55         for(int i=2;i<=cnt;i++){
56             if(x[i]!=x[i-1])x[++num]=x[i];  //去重
57         }
58         for(int i=num;i>=2;i--){
59             if(x[i]-x[i-1]>1)x[++num]=x[i]-1;  //如果两个点之间间距>1，那么在它们之间插入一个点
60         }
61         sort(x+1,x+1+num);
62         for(int i=1;i<=n;i++){
63             int le=lower_bound(x+1,x+1+num,lx[i])-x;    //找到该点离散化后的坐标
64             int ri=lower_bound(x+1,x+1+num,rx[i])-x;
65             update(1,1,num,le,ri,i);    //将这段区间染成 i
66         }
67         query(1,1,num);    //查找整个离散化后的区域总共有多少种标号
68         printf("%d
",s.size()); 
69     }
70     return 0;
71 }

2018-09-22