题目大意：题目给定一面墙（一维），在墙上贴海报，(li-ri)的区间形式张贴n张海报，求最终在墙上能看见多少张海报？
区间覆盖的线段树的求法是这样的，每个区间给定一个标记，例如(1,10),(2,6)张贴两张海报，那么(1,10)区间的节点就标记为1，(2,6)区间的节点就标记为2，这样就实现了区间覆盖，标记完之后会发现(1,1)为标记1,(2,6)为标记2,(7,10)为标记1,这样会得出三段间断的区间，怎样来将这三段区间判断为2个呢？用一个hash数组,对当前节点的标记进行1,0操作。因为每个结点都是记录的自己所在区间的标号，所以即便是这个区间被其他区间划分为K段，也可以通过对标记的1,0操作判断之前是否被标记过，若没有标记过没那么可见的海报数直接++就行了。否则不+；
题中的海报墙可是非常大的..10^7这样对于空间开销很大。这里运用到了坐标离散化的思想，将自己需要的坐标保留，不需要的剔除掉，这里可以参见LRJ黑书的切蛋糕离散化问题，但是黑书的特点就是含混不清，难以理解= =，所以看完之后我一直不知道怎么来编码实现这个问题。他给的例子也用很严重的二义性！关于离散化，网络上也没有很好的解释，因为离散化只是一种思想，对于具体题目会有不同的运用，举个例子吧，例如给定区间为(1,10000),(200,1000),很明显的，这两段区间有利用价值的就是1,200,1000,10000这四个点，直接将他们排序，对于每个下标就是他们的映射，0,1,2,3,这样比较好理解，所以在数组中存储的就是array[0]=1,arry[1]=200;这样有什么用呢？我们使用线段树进行操作的时候只是对这种数组下标进行操作，因为不管原来给定的坐标值有多大，直接映射过来为较小的数，保证相对顺序不变就可以了，也就是性质不变。原来的1->0,200>1,1000->3，我们若要执行其他的操作的话，就在这种下标去寻找原来的值就可以了。在这个题目中，只需要统计海报的总数，所以，长度便没有那么重要了。怎样去利用下标来构造树呢？之前我们存储了坐标的值，通过二分去查找坐标在数组中的位置，再将这些位置去构造二叉线段树。
对于这个题目我不懂的就是为啥，两个区间端点相差>1时，必须多插一个值？？ 觉得没有必要啊... 希望hh神犇能给我回复吧....
做完这道题，真的感觉线段树有了那么一点点的想法了，真的要活学活用啊~ 感谢hh神犇。
#include<iostream>
#include<algorithm>
#define MAXN 11111
using namespace std;int X[MAXN*3],lx[MAXN],rx[MAXN];
int col[MAXN<<4];
bool hash[MAXN<<2];
int cnt;void PushDown( int rt )
{if( col[rt]!=-1 ){col[rt<<1]=col[rt<<1|1]=col[rt];col[rt]=-1;}return ;
}int Bin( int key,int n )
{int left=0,right=n-1;while( left<=right ){int m=(left+right)>>1;if( X[m]==key )return m;if( X[m]>key )right=m-1;else left=m+1;}return -1;
}void update( int l,int r,int c,int L,int R,int rt )
{if( l<=L&&R<=r ){col[rt]=c;return ;}PushDown(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]!=-1 ){if( !hash[col[rt]] ) cnt++;hash[col[rt]]=true;return ;}if( l==r )return ;//PushDown(rt);int m=( l+r )>>1;query( l,m,rt<<1 );query( m+1,r,rt<<1|1 );
}int main()
{int T,n,nn,i;scanf( "%d",&T );while( T-- ){scanf( "%d",&n );nn=0;for( i=0;i<n;i++ ){scanf( "%d %d",&lx[i],&rx[i] );X[nn++]=lx[i];X[nn++]=rx[i];}sort( X,X+nn );int m=1;for( i=1;i<nn;i++ ){if( X[i]!=X[i-1] ) X[m++]=X[i];}for( i=m-1;i>=1;i-- ){if( X[i]!=X[i-1]+1 )X[m++]=X[i]+1;}sort( X,X+m );memset( col,-1,sizeof(col) );for( i=0;i<n;i++ ){int l=Bin( lx[i],m );int r=Bin( rx[i],m );update( l,r,i,0,m,1 );}cnt=0;memset( hash,false,sizeof(hash) );query( 0,m,1 );printf( "%d\n",cnt ); }return 0;
}