线段树的离散化，离散化就相当于是先做映射，然后再建树
对于题目给出的测试数据
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
#include
#include
#include
#include
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
??????????? 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
??????? 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;?
}?
作者：Cambridgeacm