离散化坐标然后线段树解poj2528Mayor's posters

#include<iostream>
#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
bool cmp(int a,int b)
{
	return a<b;
}
struct node
{
	int l,r;
}line[10010];
struct node1
{
	int l,r,m,w;
}tree[80010];
void create(int l,int r,int k)
{
	tree[k].l=l;
	tree[k].r=r;
	tree[k].m=(l+r)>>1;
	tree[k].w=0;
	if(l==r)
		return;
	create(l,tree[k].m,k<<1);
	create(tree[k].m+1,r,k<<1|1);
}
void join(int l,int r,int w,int k)
{
	if(tree[k].l==l&&tree[k].r==r)
	{
		tree[k].w=w;
		return;
	}
	if(tree[k].w>0)
	{
		tree[k<<1].w=tree[k<<1|1].w=tree[k].w;
		tree[k].w=-1;
	}
	else if(tree[k].w==0)
		tree[k].w=w;
	if(r<=tree[k].m)
		join(l,r,w,k<<1);
	else if(l>tree[k].m)
		join(l,r,w,k<<1|1);
	else
	{
		join(l,tree[k].m,w,k<<1);
		join(tree[k].m+1,r,w,k<<1|1);
	}
}
void in()
{
	int n,i,l,r;
	cin>>n;
	vector<int>v;
	for(i=0;i<n;i++)
	{
		cin>>line[i].l>>line[i].r;
		v.push_back(line[i].l);v.push_back(line[i].r);
	}
	sort(v.begin(),v.end(),cmp);
	v.erase(unique(v.begin(),v.end()),v.end());
	create(1,v.size(),1);
	for(i=0;i<n;i++)
	{
		l=lower_bound(v.begin(),v.end(),line[i].l)-v.begin()+1;
		r=lower_bound(v.begin(),v.end(),line[i].r)-v.begin()+1;
		join(l,r,i+1,1);
	}
}
int ans;
bool vis[20010];
void find(int k)
{
	if(tree[k].w!=-1)
	{
		if(!vis[tree[k].w])
		{
			ans++;
			vis[tree[k].w]=1;
		}
		return;
	}
	find(k<<1);
	find(k<<1|1);
}
int main()
{
	int	exp;
	cin>>exp;
	while(exp--)
	{
		in();
		ans=0;
		memset(vis,0,sizeof(vis));
		find(1);
		cout<<ans<<endl;
	}
}

离散化坐标然后线段树解poj2528Mayor's posters,布布扣,bubuko.com

离散化坐标然后线段树解poj2528Mayor's posters

原文：http://blog.csdn.net/stl112514/article/details/38535329