郁闷了一上午的题目，一直都是WA，找了老半天错，想了很多测试数据还是WA。就连骑单车回家的路上还在想这题。悲剧呀。。。
做完这个题目才明白线段树不同于其他算法，它只是一种思想，在实际应用中是要根据题意灵活去运用才行。
http://162.105.81.212/JudgeOnline/problem?id=2528
题目大意很简单，给点了区间着色，最后能看到几个区间的颜色。
此题显然是线段树的题目，不过区间有10000000那么大，冒冒失失的就去建树，然后插入是不行的。如果不离散化的话在建树与插入的时候多了太多的没必要的搜索和没必要的内存空间。
假设给定的区间是[1,3],[6,1000],我们可以如下离散
离散前坐标：1 3 6 1000
离散后坐标：1 2 3 4
于是我们就减少了没必要的搜索过程和内存空间。有个建树时的小技巧，因为我建树的每个节点是开区间到闭区间，即[a,b)。于是在读入数据的时候我就可以把b的值加一，这样就很好的处理了题目中可能出现的[a,a]相等值的区间（也就是对一个点的处理）。
在统计覆盖的时候我们可以采用倒覆盖的方式去统计。
可无论我怎么交，一直都是返回WA。直到我测试的时候发现了这组数据：
5
12 13
1 12
1 1
2 13
1 3
返回的正解应该是2，而我的是3。检查程序才发现在插入的时候如果结点左右子树都已覆盖那么它也应该是覆盖了的。举例来说如果区间[1,2),[2,4)先覆盖了，那么根节点区间[1,4)它也应该是覆盖了的。处理后就返回的是AC。。
#include <iostream>
#include <string>
using namespace std;
const int MAX_N = 20010;
struct In
{
int left;
int right;
}str[8*MAX_N];
struct Node
{
int left;
int right;
int mid;
int color;
}node[8*MAX_N];
int d[8*MAX_N];
bool boo[10000003];
int hash[10000003];
int cmp( const void *a , const void *b ){
return *(int *)a-*(int *)b;
}
void B_Tree( int left , int right , int num ){ //建树
node[num].left = left;
node[num].right = right;
node[num].mid = (left+right)/2;
node[num].color = 0;
if( left + 1 != right ){
B_Tree( left , node[num].mid , 2*num );
B_Tree( node[num].mid , right , 2*num+1 );
}
}
void insert( int left , int right , int num , int &sum ){ //插入
if( node[num].color >= node[num].right - node[num].left ){ //区间是否全部被覆盖
return ;
}
if( left == node[num].left && right == node[num].right ){
sum++;
node[num].color = node[num].right - node[num].left;
return ;
}
if( right <= node[num].mid ){
insert(left, right, 2*num , sum );
}else if( left >= node[num].mid ){
insert( left , right , 2*num+1 , sum );
}else{
insert( left , node[num].mid , 2*num , sum );
insert( node[num].mid , right , 2*num+1 , sum );
}
node[num].color = node[2*num].color + node[2*num+1].color; //根节点等于它左右子树的和
}
int main()
{
int cas , n , i , j ,m;
scanf("%d",&cas);
memset( boo , false , sizeof(boo) );
while( cas-- ){
scanf("%d",&n);
m = 0;
for( i = 1 ; i <= n ; i++ ){
scanf("%d%d",&str[i].left,&str[i].right);
str[i].right++;
if( !boo[str[i].left] ){
d[m++] = str[i].left;
boo[str[i].left] = true;
}
if( !boo[str[i].right] ){
d[m++] = str[i].right;
boo[str[i].right] = true;
}
}
qsort( d , m , sizeof(d[0]) , cmp );
j = 1;
for( i = 0 ; i < m ; i++ ){ //离散化过程
boo[d[i]] = false;
hash[d[i]] = j++;
}
int sum = 0;
B_Tree( 1 , j , 1 );
for( i = n ; i >= 1 ; i-- ){
int k = 0;
insert( hash[str[i].left] , hash[str[i].right] , 1 , k );
if( k > 0 ){
sum++;
}
}
printf("%d\n",sum);
}
return 0;
}