n（n<=10000) 个人依次贴海报,给出每张海报所贴的范围li，ri（1<=li<=ri<=10000000) 。求出最后还能看见多少张海报。

虽然之前学过离散化，但用的时候就想不起来 emm；

10000个海报 最多有10000个区间 20000个坐标值，远少于10000000，因此采用离散化

将离散化后的坐标对应数组下标储存到线段树中 ；

染色区间是整段的，本身就可以看做 lazy标记 ，需要下推函数；

 

下推 ：

void push_down(int pos){     if(  col[pos]==-1 )return ;     col[pos<<1]=col[pos<<1|1]=col[pos];     col[pos]=-1;     return ;}

染色 ：

void  updata ( int L  ,int R ,int l ,int r,int pos ,int c ){     if( l>=L && r<=R){
             col[pos] = c;         return ;     }     push_down(pos);     int mid= (l+r)>>1;     if( mid >= L) updata ( L ,R ,l ,mid ,pos<<1 ,c);     if( mid < R) updata( L ,R ,mid+1 ,r ,pos<<1|1 ,c);     return ;}

注意区间的染色情况，要在各区间坐标之间在增加一个取样；

eg： 线段树  仅采集坐标端点的线段树 1~10 -- 1~3  6~10 --1~1 3~3 6~6 10~10     

这样 如 3~6 这个区间之间的颜色就无法判断；

因此要增加离散化取样：

//离散化for( int i=0; i
     
      1)p[cnt++] =pl[i]+1;         }         sort( p , p+cnt);         int sz = unique( p ,p+cnt) - p;
     

查询：

void query( int L ,int R ,int  pos){      if( col[pos]!=-1 && ! vis[ col[pos]]){           // cout << col[pos]<<' '<
     
      <<' '<
      
       <
       
        >1;       query(L ,mid ,pos <<1 );       query( mid+1 ,R ,pos<<1|1);      return ;}
       
      
     

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int pl[10050] ,pr[10050],p[40050];int col [160050],vis[160050];int ans =0;void push_down(int pos){     if(  col[pos]==-1 )return ;     col[pos<<1]=col[pos<<1|1]=col[pos];     col[pos]=-1;     return ;}void  updata ( int L  ,int R ,int l ,int r,int pos ,int c ){     if( l>=L && r<=R){         //   cout<< pos<<" "<
         
          <
          
           >1; if( mid >= L) updata ( L ,R ,l ,mid ,pos<<1 ,c); if( mid < R) updata( L ,R ,mid+1 ,r ,pos<<1|1 ,c); return ;}void query( int L ,int R ,int pos){ if( col[pos]!=-1 && ! vis[ col[pos]]){ // cout << col[pos]<<' '<
           
            <<' '<
            
             <
             
              >1; query(L ,mid ,pos <<1 ); query( mid+1 ,R ,pos<<1|1); return ;}int bond( int n ,int x ,int y ){ int mid = x+(y-x)/2 ; while( p[mid] != n ){ if( p[mid] > n){ y = mid; } if( p[mid] < n){ x= mid+1; } mid = x+(y-x)/2 ; } return mid;}int main( ){ freopen( "out.txt" ,"w",stdout); int T; int n; scanf( "%d",&T ); while ( T--){ memset( col ,-1 ,sizeof(col)); memset( vis , 0 ,sizeof(vis)); scanf("%d",&n); int cnt=0; for( int i=0; i
              
               1)p[cnt++] =pl[i]+1; } sort( p , p+cnt); int sz = unique( p ,p+cnt) - p; // for( int i=0 ;i