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;
}