線段樹的離散化，離散化就相當於是先做映射，然後再建樹
對於題目給出的測試數據
1 4
2 6
8 10
3 4
7 10
將端點取出並且排序，去掉相同的坐標，即1，2，3，4，6，7，8，10，那麼
1，2，3，4，6，7，8，10可以離散化為
1,，2，3，4，5，6，7，8
題目給出的區間可以表示為
1 4
2 5
7 8
3 4
6 8
這樣會減小建樹的空間
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define Max 10010
struct cam1
{
int l,r;
}post[Max];
int x[Max*2];//坐標
int h[10000005];
struct cam2
{
int l,r;
int flag; //標記是否被覆蓋
}list[Max*8];
int cmp(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}
void build(int k,int l,int r)
{
list[k].l=l;
list[k].r=r;
list[k].flag=0;
if(l==r)
return;
int mid=(l+r)/2;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
}
int query(int k,int l,int r)
{
if(list[k].flag)
return 0;
if(list[k].l==l&&list[k].r==r)
{
list[k].flag=1;
return 1;
}
int result,mid;
mid=(list[k].l+list[k].r)/2;
if(r<=mid)
result=query(k<<1,l,r);
else if(l>mid)
result=query(k<<1|1,l,r);
else
result=query(k<<1,l,mid)|query(k<<1|1,mid+1,r);
if(list[k<<1].flag&&list[k<<1|1].flag) //孩子節點反饋給父親結點
list[k].flag=1;
return result;
}
int main()
{
int t,cnt;
int i,j,k,n,ans;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
cnt=0;
for(i=0;i<n;i++)
{
scanf("%d%d",&post[i].l,&post[i].r);
x[cnt++]=post[i].l;
x[cnt++]=post[i].r;
}
sort(x,x+cnt);//從小到大排序
cnt=unique(x,x+cnt)-x; //消除相同的坐標
for(i=0;i<cnt;i++)
h[x[i]]=i;
build(1,0,cnt-1);
ans=0;
for(i=n-1;i>=0;i--)
if(query(1,h[post[i].l],h[post[i].r]))
ans++; www.2cto.com
printf("%d\n",ans);
}
return 0;
}
