线段树+离散化 poj2528

题目链接

1.题目描述

有一面墙，现在需要在墙上贴广告做宣传，有N张广告，输入N组数据，代表每张广告所占的墙的范围。问：把所有广告贴好后，最多能看到多少张广告。（有的广告可能被后面贴的广告所掩盖）

1.N<10000, 墙的范围 < 107

2.思路

a.常规思路：

用一个数组表示一面墙，输入第k广告的范围i~j， 把a[i ~ j] 置为k，最后遍历整个数组，答案就是整数的个数

问题：

1. n太大，每次置为K太耗时。（利用线段树）

2. 墙的范围太大，许多不需要，只要标记就好。（离散化）

b.改进:

考虑到之前的弊端，因此在常规思路的基础上选择用：线段树+离散化

1. 离散化：将所有范围的点进行排序，有一条1到10的数轴（长度为9），给定4个区间[2,4] [3,6] [8,10] [6,9]，覆盖关系就是后者覆盖前者，每个区间染色依次为 1 2 3 4。

现在我们抽取这4个区间的8个端点，2 4 3 6 8 10 6 9

然后删除相同的端点，这里相同的端点为6，则剩下2 4 3 6 8 10 9

对其升序排序，得2 3 4 6 8 9 10

然后建立映射

2 3 4 6 8 9 10

↓ ↓ ↓ ↓ ↓ ↓ ↓

1 2 3 4 5 6 7

那么新的4个区间为 [1,3] [2,4] [5,7] [4,6]，覆盖关系没有被改变。新数轴为1到7，即原数轴的长度从9压缩到6，显然构造[1,7]的线段树比构造[1,10]的线段树更省空间，搜索也更快，但是求解的结果却是一致的。

离散化时有一点必须要注意的，就是必须先剔除相同端点后再排序，这样可以减少参与排序元素的个数，节省时间。

2. 线段树：就是常规思路

3.代码如下

#include<cstdio>  
#include<map>  
#include<set>   
#include<algorithm>  
using namespace std;  
map<int,int>mp;  
set<int>st;   
int cmp(int a,int b)  
{  
    return a<b;  
}  
int a[],c[],x[],y[];  
void down(int i)  
{  
     if(c[i])  
     {  
             c[*i]=c[*i+]=c[i];  
             c[i]=;  
     }  
}   
void build(int i,int l,int r)  
{  
     c[i]=;  
     if(l==r)  
     return;  
     int m=(l+r)>>;  
     build(*i,l,m);  
     build(*i+,m+,r);  
}  
void ud(int i,int l,int r,int L,int R,int x)  
{  
     if(l==L&&r==R)  
     {  
                   c[i]=x;  
                   return;  
     }  
     down(i);  
     int mid=(L+R)>>;  
     if(mid>=r)  
     ud(*i,l,r,L,mid,x);   
     else if(mid<l)  
     ud(*i+,l,r,mid+,R,x);   
     else  
     {  
         ud(*i,l,mid,L,mid,x);   
         ud(*i+,mid+,r,mid+,R,x);  
     }  
}  
void dfs(int i,int l,int r)         
{  
     if(c[i])  
     {  
             st.insert(c[i]);  
             return;   
     }              
     if(l==r)  
     return;   
     int m=(l+r)>>;   
     dfs(*i,l,m);  
     dfs(*i+,m+,r);  
}   
int t,n;  
int main()  
{  
    scanf("%d",&t);  
    while(t--)  
    {  
              int n;  
              scanf("%d",&n);  
              mp.clear();  
              st.clear();   
              int j=;  
              for(int i=;i<=n;i++)  
              {  
                      int q,w;  
                      scanf("%d%d",&q,&w);  
                      x[i]=q,y[i]=w;  
                      a[++j]=q;  
                      a[++j]=w;  
              }  
              sort(a+,a+*n+,cmp);  
              int z=;  
              for(int i=;i<=*n;i++)  
              {  
                     while(i!=*n&&a[i]==a[i+])i++;  
                     mp[a[i]]=++z;   
              }  
              build(,,z);  
              for(int i=;i<=n;i++)  
              {  
                      ud(,mp[x[i]],mp[y[i]],,z,i);  
              }   
              dfs(,,z);   
              printf("%d\n",st.size());  
    }  
    return ;  
}