离散化 的大概思路 :   比如说给你一组 数据 1 4 1000 100000，  如果直接

                         开线段, 显然是浪费, 那么我们只要 进行 映射 :

                                1    1  

                                4    2

                             1000    3

                           100000    4

                         接下来 我们只要对 1 2 3 4 建立线段树就行了 只需要

                         [1,4]的区间     

离散化就相当于是先做映射，然后再建树。

本题大意：给定一些海报，可能相互重叠，告诉你每个海报的宽度（高度都一样的）和先后叠放顺序，问没有被完全盖住的有多少张？

海报最多10000张，但是墙有10000000块瓷砖长，海报不会落在瓷砖中间。

如果直接建树，就算不TLE,也会MLE。即单位区间长度太多。

其实10000张海报，有20000个点，最多有19999个区间。对各个区间编号，就是离散化。然后建数。

其实浮点数也是一样离散化的。

 

 

刚开始离散化利用map，果断tle了

改了就过了

 

#include
     
      #include
      
       #include
       
        #include
        
         #define ll long long#define ull unsigned long long#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;const int maxn=20000+20;struct Seg{    int l,r;};Seg seg[maxn>>1];struct Gao{    int v,dir,id,num;};Gao gao[maxn];bool vis[maxn>>1];int val[maxn<<2];int lazy[maxn<<2];int ans;int solve(int ,int );int main(){    int test;    scanf("%d",&test);    while(test--){        int n;        scanf("%d",&n);        int len=0;        for(int i=1;i<=n;i++){            int u,v;            scanf("%d %d",&u,&v);            seg[i].l=u,seg[i].r=v;            gao[++len].v=u,gao[len].dir=0,gao[len].id=i;            gao[++len].v=v,gao[len].dir=1,gao[len].id=i;        }        printf("%d\n",solve(n,len));    }    return 0;}bool cmp(Gao x,Gao y){    return x.v
         
          =r){        lazy[rt]=add;        val[rt]=add;        return ;    }    pushdown(rt);    int m=(l+r)>>1;    if(L<=m)        update(L,R,add,lson);    if(R>m)        update(L,R,add,rson);    pushup(rt);}void query(int l,int r,int rt){    if(!val[rt])        return ;    if(val[rt]>0){        if(!vis[val[rt]]){            ans++;            vis[val[rt]]=true;        }        return ;    }    pushdown(rt);    int m=(l+r)>>1;    query(lson);    query(rson);}int solve(int n,int len){    sort(gao+1,gao+len+1,cmp);    int tot=0;    gao[1].num=++tot;    for(int i=2;i<=len;i++){        if(gao[i].v==gao[i-1].v)            gao[i].num=tot;        else            gao[i].num=++tot;    }    for(int i=1;i<=len;i++){        if(!gao[i].dir){            seg[gao[i].id].l=gao[i].num;        }        else{            seg[gao[i].id].r=gao[i].num;        }    }    memset(val,0,sizeof val);    memset(lazy,0,sizeof lazy);    for(int i=1;i<=n;i++){        update(seg[i].l,seg[i].r,i,1,tot,1);    }    memset(vis,false,sizeof vis);    ans=0;    query(1,tot,1);    return ans;}