线段树+离散化

有些数据本身很大， 自身无法作为数组的下标保存对应的属性。如果这时只是需要这堆数据的相对属性， 那么可以对其进行离散化处理！

离散化：当数据只与它们之间的相对大小有关，而与具体是多少无关时，可以进行离散化。

使用STL中的unique进行去重(条件是重复的元素一定相邻)，然后再用STL中的二分函数lower_bound找出具体的插入位置，一般是这种写法

sort(X,X+num);
int m=unique(X,X+num)-X;//离散化
for(int i=0; i<n; i++)
{
    int l=lower_bound(X,X+m,li[i])-X;//寻找位置
    int r=lower_bound(X,X+m,ri[i])-X;
    update(l,r,i,0,m,1);
}

例题：

POJ2528 Mayor's posters(线段树区间更新，离散化)

在一面长度为很长很长的墙上贴海报，每张海报的高度一样，唯一的区别是贴海报的位置不同，问最后能看见几张海报。

因为墙的长度长，直接线段树可能超时，所以要进行离散化处理，将离散后的坐标映射到线段树中，并不影响最后所求的海报长度.在这道题中，因为海报是按照段来算的，而不是点，所以可能会出现离散化之后有缝隙的问题,比如:[1,10]、[1,3]、[6,10]离散化之后是[1,4]、[1,2]、[3,4]这样会导致2和3之间的缝隙丢失导致错误，所以再去重完毕后，进行一个处理,如果相邻数字间距大于1的话,在其中加上任意一个数字。这样会把原来的缝隙留出来.

线段树的作用是利用lazy标记，当需要覆盖的时候，就把当前这一段区间的lazy变成当前第几张海报的标号，查询的时候只需要利用一个数组标记一下当前点是否访问过且有lazy标记，有的话就记录一下数量

#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long ll;
const int N=10000+50;
int lazy[N<<4];
int vis[N],li[N],ri[N],X[N<<2];
int cnt;
void pushdown(int rt)//下放lazy
{
    if(~lazy[rt])
    {
        lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt];
        lazy[rt]=-1;
    }
}
void update(int L,int R,int c,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        lazy[rt]=c;
        return;
    }
    pushdown(rt);
    int m=(l+r)>>1;
    if(L<=m) update(L,R,c,lson);
    if(R>m) update(L,R,c,rson);
}
void query(int l,int r,int rt)
{
    if(~lazy[rt])
    {
        if(!vis[lazy[rt]])
            cnt++;
        vis[lazy[rt]]=1;
        return;
    }
    if(l==r) return;
    int m=(l+r)>>1;
    query(lson);
    query(rson);
}

int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int num=0;
        for(int i=0; i<n; i++)
        {
            scanf("%d%d",&li[i],&ri[i]);
            X[num++]=li[i];
            X[num++]=ri[i];
        }
        sort(X,X+num);
        int m=unique(X,X+num)-X;//离散化
        for(int i=m-1; i>0; i--)//有缝隙的情况
            if(X[i]!=X[i-1]+1)
                X[m++]=X[i-1]+1;
        sort(X,X+m);
        mem(lazy,-1);
        for(int i=0; i<n; i++)
        {
            int l=lower_bound(X,X+m,li[i])-X;//寻找位置
            int r=lower_bound(X,X+m,ri[i])-X;
            update(l,r,i,0,m,1);
        }
        cnt=0;
        mem(vis,0);
        //查询[0,m]区间个数
        query(0,m,1);
        printf("%d\n",cnt);
    }
    return 0;
}