線段樹+離散化 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 ;  
}