POJ-2528-Mayor's posters

POJ-2528-Mayor's posters

http://poj.org/problem?id=2528

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

对于题目给出的测试数据

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

这样会减小建树的空间

#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++;
		printf("%d\n",ans);
	}
	return 0;
}