【BZOJ1818】[Cqoi2010]内部白点

Description

无限大正方形网格里有n个黑色的顶点，所有其他顶点都是白色的（网格的顶点即坐标为整数的点，又称整点）。每秒钟，所有内部白点同时变黑，直到不存在内部白点为止。你的任务是统计最后网格中的黑点个数。内部白点的定义：一个白色的整点P(x,y)是内部白点当且仅当P在水平线的左边和右边各至少有一个黑点（即存在x1 < x < x2使得(x1,y)和(x2,y)都是黑点），且在竖直线的上边和下边各至少有一个黑点（即存在y1 < y < y2使得(x,y1)和(x,y2)都是黑点）。

Input

输入第一行包含一个整数n，即初始黑点个数。以下n行每行包含两个整数(x,y)，即一个黑点的坐标。没有两个黑点的坐标相同，坐标的绝对值均不超过109。

Output

输出仅一行，包含黑点的最终数目。如果变色过程永不终止，输出-1。

Sample Input

4
0 2
2 0
-2 0
0 -2

Sample Output

5
数据范围
36%的数据满足：n < = 500
64%的数据满足：n < = 30000
100%的数据满足：n < = 100000

题解：容易发现，对于x坐标相同的点，最有用的点一定是y坐标最小和最大的点；y相同的，最有用的就是x坐标最小和最大的点。并且新加入的内部白点的x和y坐标一定不会比原来更优，所以。。。变色过程只持续了最多1秒。

于是我们先离散化，求出x坐标相同时y的最小值和最大值以及y相同时x的最小最大值，然后可以看成给你一堆线段求这些线段的交点个数。用扫描线+树状数组即可。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

const int maxn=100010;

typedef long long ll;

int n,mx,my;

ll ans;

int xl[maxn],xr[maxn],yl[maxn],yr[maxn],s[maxn];

struct point

{

	int x,y;

}p[maxn];

struct node

{

	int val,org;

}num[maxn];

vector<int> q1[maxn],q2[maxn];

vector<int>::iterator it;

bool cmpv(const node &a,const node &b)

{

	return a.val<b.val;

}

bool cmpx(const point &a,const point &b)

{

	return a.x<b.x;

}

inline void updata(int x,int val)

{

	for(int i=x;i<=mx;i+=i&-i)	s[i]+=val;

}

inline int query(int x)

{

	int i,ret=0;

	for(i=x;i;i-=i&-i)	ret+=s[i];

	return ret;

}

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')	f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+(gc^'0'),gc=getchar();

	return ret*f;

}

int main()

{

	n=rd();

	int i;

	for(i=1;i<=n;i++)	num[i].val=rd(),p[i].y=rd(),num[i].org=i;

	sort(num+1,num+n+1,cmpv);

	for(i=1;i<=n;i++)

	{

		if(i==1||num[i].val>num[i-1].val)	mx++;

		p[num[i].org].x=mx;

	}

	for(i=1;i<=n;i++)	num[i].val=p[i].y,num[i].org=i;

	sort(num+1,num+n+1,cmpv);

	for(i=1;i<=n;i++)

	{

		if(i==1||num[i].val>num[i-1].val)	my++;

		p[num[i].org].y=my;

	}

	memset(xl,0x3f,sizeof(xl)),memset(yl,0x3f,sizeof(yl));

	for(i=1;i<=n;i++)

	{

		xr[p[i].x]=max(xr[p[i].x],p[i].y),xl[p[i].x]=min(xl[p[i].x],p[i].y);

		yr[p[i].y]=max(yr[p[i].y],p[i].x),yl[p[i].y]=min(yl[p[i].y],p[i].x);

	}

	for(i=1;i<=mx;i++)	q1[xl[i]].push_back(i),q2[xr[i]].push_back(i);

	for(i=1;i<=my;i++)

	{

		for(it=q1[i].begin();it!=q1[i].end();it++)	updata(*it,1);

		ans+=query(yr[i])-query(yl[i]-1);

		for(it=q2[i].begin();it!=q2[i].end();it++)	updata(*it,-1);

	}

	printf("%lld",ans);

	return 0;

}

内部白点