题目网址：http://poj.org/problem?id=2528
题意：
n（n<=10000)个人依次贴海报,给出每张海报所贴的范围li，ri（1<=li<=ri<=10000000)。
求出最后还能看见多少张海报。
输入：
1
5
1 4
2 6
8 10
3 4
7 10
这题用常规思路解题必定ＴＬＥ，l,r太大；
通俗点说，离散化就是压缩区间，使原有的长区间映射到新的短区间，但是区间压缩前后的覆盖关系不变。举个例子：
有一条1到10的数轴（长度为9），给定4个区间[2,4] [3,6] [8,10] [6,9]，覆盖关系就是后者覆盖前者，每个区间染色依次为 1 2 3 4。
现在我们抽取这4个区间的8个端点，2 4 3 6 8 10 6 9
然后删除相同的端点，这里相同的端点为6，则剩下2 4 3 6 8 10 9
对其升序排序，得2 3 4 6 8 9 10
然后建立映射
2 3 4 6 8 9 10
↓ ↓ ↓ ↓ ↓ ↓ ↓
1 2 3 4 5 6 7
那么新的4个区间为 [1,3] [2,4] [5,7] [4,6]，覆盖关系没有被改变。新数轴为1到7，即原数轴的长度从9压缩到6，显然构造[1,7]的线段树比构造[1,10]的线段树更省空间，搜索也更快，但是求解的结果却是一致的。
离散化时有一点必须要注意的，就是必须先剔除相同端点后再排序，这样可以减少参与排序元素的个数，节省时间。
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
#define N 10100
#define M 10000000
bool vis[*N];//标记出现过得海报
int x[*N];
struct T
{
int node,add,l,r;
}tree[M*];
void creat(int l,int r,int k)//建树
{
tree[k].node=;
tree[k].l=l;
tree[k].r=r;
tree[k].add=;
if(l==r)
return;
int mid=(l+r)>>;
creat(l,mid,k<<);
creat(mid+,r,k<<|);
}
void pushdown(int k,int color)//延迟标记
{
int x=k<<;
tree[x].add=;
tree[x+].add=;
tree[x].node=color;
tree[x+].node=color;
tree[k].add=;
tree[k].node=;
}
void Search(int l,int r,int color,int k)//更新线段树
{
if(r<tree[k].l||l>tree[k].r)
return ;
if(l<=tree[k].l&&r>=tree[k].r)
{
tree[k].node=color;
tree[k].add=;
return ;
}
if(tree[k].add)
pushdown(k,tree[k].node);
int mid=(tree[k].l+tree[k].r)>>;
if(r<=mid)
Search(l,r,color,k<<);
else if(l>mid)
Search(l,r,color,k<<|);
else
{
Search(l,mid,color,k<<);
Search(mid+,r,color,k<<|);
}
}
int ans;
void q(int l,int r,int k)//查找不同颜色的区域
{
if(tree[k].add)
{
if(!vis[tree[k].node])
{
ans++;
vis[tree[k].node]=;
}
return ;
}
int mid=(l+r)>>;
q(l,mid,k<<);
q(mid+,r,k<<|);
}
int s(int l,int r,int k)//二分查找
{
int mid;
while(l<=r)
{
mid=(l+r)>>;
if(k<x[mid]) r=mid-;
else if(k>x[mid]) l=mid+;
else return mid;
}
return -;
}
int main()
{
int t,n,i,j;
int l[N],r[N];
scanf("%d",&t);
while(t--)
{
j=;
memset(vis,,sizeof(vis));
scanf("%d",&n);
for(i=;i<n;i++)
{
scanf("%d%d",&l[i],&r[i]);
x[j++]=l[i];
x[j++]=r[i];
}
sort(x,x+j);
int m=;
for(i=;i<j-;i++)
{
if(x[i]==x[i+])
{
m--;
}
else
{
x[i+m]=x[i+];
}
}
j=j+m-;
sort (x,x+j);
/*for(i=0;i<n;i++)
{
printf("%d %d ",s(0,j-1,l[i])+1,s(0,j-1,r[i])+1);
cout<<endl;
}*/
creat(,j,);
for(i=;i<n;i++)
{
Search(s(,j-,l[i])+,s(,j-,r[i])+,i+,);
}
ans=;
q(,j,);
printf("%d\n",ans);
}
return ;
}