POJ2528+线段树

见代码。

 /*

 线段树+Lazy

 题意：有一面墙，被等分为1QW份，一份的宽度为一个单位宽度。

 现在往墙上贴N张海报，每张海报的宽度是任意的，但是必定是单位宽度的整数倍，且<=1QW。

 后贴的海报若与先贴的海报有交集，后贴的海报必定会全部或局部覆盖先贴的海报。

 现在给出每张海报所贴的位置（左端位置和右端位置），问张贴完N张海报后，还能看见多少张海报？

 （PS：看见一部分也算看到。）

 */

 #include<stdio.h>

 #include<string.h>

 #include<stdlib.h>

 #include<algorithm>

 #include<iostream>

 #include<queue>

 #include<map>

 #include<stack>

 #include<set>

 #include<math.h>

 using namespace std;

 typedef long long int64;

 //typedef __int64 int64;

 typedef pair<int64,int64> PII;

 #define L(x) (x<<1)

 #define R(x) (x<<1|1)

 #define MP(a,b) make_pair((a),(b))

 const int maxn = ;

 const int inf = 0x7fffffff;

 const double pi=acos(-1.0);

 const double eps = 1e-;

 struct Node{

     int L,R,color;

 }tree[ maxn<< ];

 struct NODE{

     int L,R;

     bool operator<(const NODE &tmp ) const{

         return R<tmp.R;

     }

 }a[ maxn ];

 int myhash[ maxn ];

 int ANS;

 int vis[ maxn ];

 int lisanhua( int k ){

     sort( myhash,myhash+k );

     int cnt = unique( myhash,myhash+k ) - myhash;

     return cnt;

 }

 void build( int L,int R,int n ){

     if( L==R ){

         tree[ n ].L = L;

         tree[ n ].R = R;

         tree[ n ].color = ;

         return ;

     }

     tree[ n ].L = L;

     tree[ n ].R = R;

     tree[ n ].color = ;

     int mid = (L+R)/;

     build( L,mid,L(n) );

     build( mid+,R,R(n) );

 }

 void PushDown( int n,int new_color ){

     if( tree[ n ].color!=&&tree[ n ].color!=new_color ){

         tree[ L(n) ].color = tree[ R(n) ].color = tree[ n ].color;

         tree[ n ].color = ;

     }

 }

 void update( int x,int y,int new_color,int L,int R,int n ){

     if( x==L&&y==R ){

         tree[ n ].color = new_color;

         return ;

     }

     PushDown( n,new_color );

     int mid = (L+R)/;

     if( mid>=y ) update( x,y,new_color,L,mid,L(n) );

     else if( mid<x ) update( x,y,new_color,mid+,R,R(n) );

     else {

         update( x,mid,new_color,L,mid,L(n) );

         update( mid+,y,new_color,mid+,R,R(n) );

     }

 }

 void query( int n ){

     if( tree[n].color ){

         if( vis[tree[n].color]== ){

             vis[tree[n].color] = ;

             ANS++;

         }

         return ;

     }

     //int mid = (tree[n].L+tree[n].R)/2;

     query( L(n) );

     query( R(n) );

 }

 int main(){

     int T;

     scanf("%d",&T);

     while( T-- ){

         int n;

         scanf("%d",&n);

         int k = ;

         for( int i=;i<=n;i++ ){

             scanf("%d%d",&a[i].L,&a[i].R);

             myhash[ k++ ] = a[i].L;

             myhash[ k++ ] = a[i].R;

         }

         int cnt = lisanhua( k );

         build( ,cnt, );

         //printf("build\n");

         for( int i=;i<=n;i++ ){

             int x = lower_bound( myhash,myhash+cnt,a[i].L )-myhash;

             int y = lower_bound( myhash,myhash+cnt,a[i].R )-myhash;

             x++,y++;

             //printf("i = %d\n",i);

             //printf("x = %d, y=%d\n",x,y);

             update( x,y,i,,cnt, );

         }

         ANS = ;

         memset( vis,,sizeof( vis ) );

         //printf("query\n");

         query(  );

         printf("%d\n",ANS);

     }

     return ;

 }