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;
}