看到了很多人说离散化，一开始不太明白到底是什么意思！直到昨天晚上看完了 poj 2528 染色问题
怎么说呢，个人觉得应该是把那些离散的点聚合吧，我们要把两个不相同的相邻的点的距离变成1，那么如果我们有一些列的点如：1 2 3 4 6 7 8 19 聚合化以后变成了，0 1 2 3 4 5 6 7，这就说我们把原来的大区间相同化为了小点的区间，前提这两个区间在某方面是等价的！
还有我个人一开始写的线段树，写的很差，根本没有发挥线段树的主要优点，所以一开始是TLE，我写的是对点操作了，而非对线段或者区间操作，所以完全没有发挥线段树的优点！很是不爽，自以为自己弄明白了线段树！还是得看看资料理解下！思考，这道题暂时留着不A了！
个人对离散话的理解是：把大区间转化成小区间！如果有什么错误的，望请告知！谢谢！
我要睡觉去了，先找个题看看，然后就睡觉去了！晚安！各位！
等我完全弄明白了线段树，再把这题的解题报告写出来！
一开始以为自己到底是怎么了，怎么搞不定这题呢，而且一开始TLE，这个我能理解，因为后来我才发现了，我处理的不是对线段处理的，而还是对点处理的，当然TLE ，然后我就仔细的看了下别人的代码，发现其实我们没有什么不同的，就只有 聚合化（本人理解 觉得不应该叫做 离散话，如果你知道为什么叫做 离散话 请告诉我，虽然 lrj上的，火星地图， 我觉得用离散化这个词倒是对，这里应该叫做聚合化，纯属个人理解！错误请指正！谢谢！）后 涂色 不一样，所以我TLE，我是：如果a-b区间要涂色，我就更新到每个的a-b之间的
点，这样肯定是不行的，还不如不用线段树，完全没有发挥，线段树区间的性质！这也说明，线段树我还没有学明白!
这里加上一个注意吧，个人理解一般来说，对线段树的操作，很少是到达叶子的！而是大部分对某一区间进行操作的！一定要记住这点，可别把线段树，当作数组来操作了，那就没有意义了！
下面是我的代码，是参考别人写的，个人觉得主要是 post() 函数，我一开始就是写错了，根本就没有理解和发挥线段树的效率，所以TLE！线段树的知识还是需要多加练习与学习！
#include<stdio.h>
#include<memory.h>
#include<algorithm>
#include<iostream>
using namespace std ;
#define N 10005
struct datanode
{
int f , t ;
} datain[N] ;
int n ; // the numbers of poster
int m ; // the small area
int datasort[N*2] ; // for smaller
int colornums ; // the numbers of the end
int judge[N*2] ; // for judge the rest of color
struct tnode
{
int from , to ;
int color ; // the color from the area of "from" to "to" 0 no post , >= 1 is post color
} t[N*8] ;
void create( int st , int ed , int r )
{
t[r].from = st ;
t[r].to = ed ;
t[r].color = 0 ;
if( st == ed )
return ;
int mid = ( st + ed ) >> 1 ;
create( st , mid , r *2 ) ;
create( mid+1 , ed , r*2+1 ) ;
}
void post( int st , int ed , int c , int r )
{
if( t[r].from == st && t[r].to == ed )
{
t[r].color = c ;
return ;
}
if( t[r].color != -1)
{
t[r*2].color = t[r].color ;
t[r*2+1].color = t[r].color ;
t[r].color = -1 ;
}
int mid = ( t[r].from + t[r].to ) >> 1 ;
if( mid >= ed )
{
post( st ,ed , c , r * 2 ) ;
}
else if( mid < st )
{
post( st , ed , c , r*2+1 ) ;
}
else
{
post( st , mid , c , r * 2 ) ;
post( mid+1 , ed , c , r *2 +1 ) ;
}
}
int b_search( int k )
{
int left = 0 , right = m - 1 ;
int mid = ( left + right ) >> 1 ;
while( k != datasort[mid] )
{
if( k < datasort[mid] )
{
right = mid -1 ;
}
else
{
left = mid + 1 ;
}
mid = ( left + right ) >> 1 ;
}
return mid ;
}
void howmany( int r )
{
if( t[r].color == -1)
{
howmany( r*2 ) ;
howmany( r*2+1) ;
}
else
{
if( ! judge[ t[r].color ] )
{
//cout<<t[r].from<<" "<<t[r].to<<" "<<t[r].color<<endl;
colornums ++ ;
judge[ t[r].color ] = 1 ;
}
return ;
}
}
int main()
{
int ntc ;
int i , j ;
scanf( "%d" , & ntc ) ;
int ff , tt ;
while( ntc --)
{
scanf( "%d" , & n ) ;
for( i = 0 ; i< n ; i++ )
{
scanf( "%d%d" , & datain[i].f , & datain[i].t) ;
datasort[i*2] = datain[i].f ;
datasort[i*2+1] = datain[i].t ;
}
sort( datasort , datasort+(2*n) ) ;
m = 1 ;
for( j = 1 ; j< 2*n ; j++ )
{
if( datasort[j-1] != datasort[j] )
datasort[m++] = datasort[j] ;
}
create( 0 , m-1 , 1 ) ;
for( i = 0 ; i< n ; i++ )
{
ff = b_search( datain[i].f ) ;
tt = b_search( datain[i].t ) ;
post( ff , tt , i+1 , 1 ) ;
}
colornums = 0 ;
memset( judge , 0 , sizeof( judge ) );
judge[0] = 1 ;
howmany( 1) ;
printf("%d\n" , colornums ) ;
}
return 0 ;
}