NYOJ地址：
http://acm.nyist.net/JudgeOnline/problem.php?pid=9题意：往区间[1,
10000000]的墙上贴海报，海报数量的区间是[1,10000]，后贴的会覆盖之前的，问最后能看到的海报数量。
思路：离散化+线段树。10000000的区间如果直接用线段树写的话肯定会MLE，海报的数量最多为10000张，也就说最多有20000个点，可以先用离散化处理。这是我第一次写离散化，仿照了大牛的blog才搞定。 我在poj提交了一个错误的离散化代码居然过了，在自己学校的oj没有过，后来加了空隙处理才过掉。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN=30003;
inline int L(int r){return r<<1;}
inline int R(int r){return ((r<<1)+1);}
inline int MID(int l,int r) {return (l+r)>>1;}
typedef struct
{
int left,right;
int value;
}LINE;
LINE tree[MAXN*4];
typedef struct NODE
{
int value,zy;
bool operator < (const NODE& r) const
{
return value<r.value;
}
}NODE;
NODE node[MAXN];
int post[MAXN][2];
bool flag[MAXN];
int sum;
void Create(int l,int r,int root) //建树
{
tree[root].left=l;
tree[root].right=r;
tree[root].value=0;
if(l==r) return;
int mid=MID(l,r);
Create(l,mid,L(root));
Create(mid+1,r,R(root));
}
void Update(int l,int r,int v,int root) //更新
{
if(l<=tree[root].left&&tree[root].right<=r)
{
tree[root].value=v;
return;
}
if(tree[root].left==tree[root].right) return;
if(tree[root].value==v)return;
if(tree[root].value>0)
{
tree[L(root)].value=tree[root].value;
tree[R(root)].value=tree[root].value;
tree[root].value=0;
}
int mid=MID(tree[root].left,tree[root].right);
if(l>mid) Update(l,r,v,R(root));
else if(r<=mid) Update(l,r,v,L(root));
else
{
Update(l,mid,v,L(root));
Update(mid+1,r,v,R(root));
}
}
void solve(int r) //询问
{
if(tree[r].value)
{
if(!flag[tree[r].value])
{
sum++;
flag[tree[r].value]=1;
}
return;
}
solve(L(r));
solve(R(r));
}
int main()
{
//freopen("input","r",stdin);
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d%d",&post[i][0],&post[i][1]);//当前post为左右界坐标真值
node[L(i)].zy=-i-1;//左值为负
node[R(i)].zy=i+1;//右值为正
node[L(i)].value=post[i][0];//把左右界坐标真值储存在结构体数组中
node[R(i)].value=post[i][1];
}
sort(node,node+n*2);//对所有坐标进行排序
int count=1,temp=node[0].value;//count为离散化后坐标值。
for(int i=0;i<2*n;i++)
{
if(node[i].value!=temp)//如果坐标不同，则坐标加1
{
count++;
temp=node[i].value;
if(i!=0) //空隙处理，写的不是很好
if(node[i-1].zy>0)
if((node[i-1].value+1)!=node[i].value)
count++;
}
if(node[i].zy<0) post[-node[i].zy-1][0]=count;//新post为离散化过后，左右界值
else post[node[i].zy-1][1]=count;
}
memset(flag,0,sizeof(flag));
Create(1,count,1);
for(int i=0;i<n;i++)
Update(post[i][0],post[i][1],i+1,1);
sum=0;
solve(1);
printf("%d\n",sum);
}
return 0;
}