POJ-2528-Mayor's posters

线段树的离散化，离散化就相当于是先做映射，然后再建树

对于题目给出的测试数据

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

作者：Cambridgeacm