Mayor's posters 線段樹+離散化

題目位址：http://poj.org/problem?id=2528

首先第一行要輸入c，表示進行c個測試案例。題意大體是有n(1 <= n <= 10000)個人往牆上貼海報，每個人給出貼的範圍li,ri( 1 <= l i <= ri <= 10000000)，問最後還能看見多少海報（完整的不完整的都算）.

 先說一下什麼是離散化，如果線段樹要開的區間很大，但是線段樹又開不了那麼大，或者開了之後肯定會MLE或者TLE，那這時候就要考慮離散化了。通俗點說，離散化就是壓縮區間，使原有的長區間映射到新的短區間，但是區間壓縮前後的覆寫關系不變。

例如：有一條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]的線段樹更省空間，搜尋也更快，但是求解的結果卻是一緻的。（轉自https://www.cnblogs.com/zhangmingcheng/p/3940986.html）

（注意！！！！！！數字代表的是線段，不是點） 

有時候隻是普通的離散化是不行的，舉個例子，【1,4】，【2,8】，【7,10】，離散化之後是【1,3】，【2,5】，【4,6】，沒離散化之前一共是3，離散化之後是2，原因是離散化之後原本不相鄰的點變成了相鄰的點，解決的方法就是在原本不相鄰的兩個點之間加一個數，把這兩個點變成和原來一樣是不相鄰的。

AC代碼：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;
const int maxn=200000;
int col[maxn<<2];
int now[maxn<<2];
bool vis[maxn];
int ans;
struct tree
{
    int ls,rs;
};
tree t[maxn];
void pushup(int rt)
{
    if(col[rt])
    {
        col[rt<<1]=col[rt<<1|1]=col[rt];//把父節點的資訊傳給子節點
        col[rt]=0;
    }
}
void update(int L,int R,int c,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        col[rt]=c;
        return ;
    }
    pushup(rt);//想一下，因為是把父節點的顔色給下面的子節點，是以要先更新，再遞歸
    int m=(l+r)>>1;
    if(L<=m)
        update(L,R,c,l,m,rt<<1);
    if(R>m)
        update(L,R,c,m+1,r,rt<<1|1);

}
void Query(int l,int r,int rt)
{
    if(col[rt])//我自己的了解，這時候的rt隻有一種顔色，因為父節點的的資訊都傳給子節點并且父節點的col[rt]都賦0了
    {
        if(!vis[col[rt]])
        {
            ans++;
            vis[col[rt]]=1;//标記，同一種顔色加一次
        }
        return ;
    }
    if(l==r)
        return ;
    int m=(l+r)>>1;
    Query(l,m,rt<<1);
    Query(m+1,r,rt<<1|1);
}
int main()
{
    int c;
    scanf("%d",&c);
    while(c--)
    {
        int n;
        scanf("%d",&n);
        int cnt=0;
        memset(vis,0,sizeof(vis));
        memset(col,0,sizeof(col));
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&t[i].ls,&t[i].rs);//把每條線段單獨儲存，并把左右端點記錄。
            now[cnt++]=t[i].ls;
            now[cnt++]=t[i].rs;
        }
        sort(now,now+cnt);//排序
        cnt=unique(now,now+cnt)-now;//去重
        for(int i=cnt-1;i>0;i--)//在原本不相鄰的兩個數之前加一個數，加到最後就可以，因為後面還要排序
        {
            if(now[i]!=now[i-1]+1)
                now[cnt++]=now[i]-1;
        }
        sort(now,now+cnt);
        for(int i=0;i<n;i++)//找到現在每個廣告商左右端點對應的位置
        {
            int l=lower_bound(now,now+cnt,t[i].ls)-now;
            int r=lower_bound(now,now+cnt,t[i].rs)-now;
            update(l+1,r+1,i+1,1,cnt,1);//數組和線段樹左右端點想相一緻，這裡線段樹是從1到cnt，因為數組下标是從0開始的，是以要加1。
        }
        ans=0;
        Query(1,cnt,1);
        printf("%d\n",ans);
    }
    return 0;
}