Link
Description
一个平面直角坐标系内有 \(n\) 个黑点，其余点为白点，将会进行若干次变换，每次变换会把上下左右方向都有黑点的白点变成黑点，直到找不到符合要求的白点。
问最终有多少黑点。若变换过程永不停止，输出 -1。
Solution
首先看一个结论：在任何情况下，最多只会变换一次。
简证：假设存在一个点 \(A\)，它是经过两次变换得到的，那么它的四个方向中至少有一个点是经过一次变换得到的（否则点 \(A\) 也应当在第一次变换时被染成黑色）。
设这个点为 \(B\)，那么点 \(B\) 应当是四个原始的黑点染成黑色的并且是 \(A\) 向 \(B\) 方向上唯一的黑点。
然而这意味着 \(A\) 向 \(B\) 方向就会有另一个原始黑点。矛盾。（如下图，红点即为矛盾点）
那么问题就转化为：有多少个白点满足其上下左右方向都有黑点。
不难看出，这就是询问将所有水平/竖直方向的点用线段连接起来之后，横竖方向的线段之间能形成多少个交点（在端点处相交不算）。
设一条横着的线段从 \((x_1,y_1)\) 到 \((x_2,y_1)\)，另一条竖着的线段从 \((x_3,y_2)\) 到 \((x_3,y_3)\)，那么它们能形成交点的充要条件为 \(\begin{cases}x_3 \in [x_1+1,x_2-1] \\ y_1 \in [y_2+1,y_3-1]\end{cases}\)。
于是使用扫描线：将所有横向线段按照 \(y\) 坐标排序后将 \(y\) 轴看作时间轴，把竖着的线段看作单点修改（下端点 \(+1\) 上端点 \(-1\)）（相当于表示从下端点到上端点这段时间内，在这条线段的 \(x\) 坐标处有一条线段），此时横着的线段可以看作询问 \([l+1,r-1]\) 之间的和（\(l\) 为区间左端点，\(r\) 为区间右端点）（相当于询问这个区间内有多少条竖着的线段），开一个树状数组维护即可。
但是考虑到坐标范围 \(10^9\)，于是先离散化。
Code
#include<cstdio>
#include<algorithm>
const int M=1e5+5;
inline int read(){int x(0),op(0);char ch=getchar();while(ch<'0'||ch>'9')op|=(ch==45),ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return op?-x:x;}
struct line{
int l,r,h,w;
bool operator < (const line& rhs){
return h<rhs.h;
}
}L[M*3];//luogu的数据好像略水，我在校内OJ上交的时候开2e5会RE，分析之后应该是L数组要开成3e5否则全部是修改操作会炸
struct point{
int x,y;
}P[M];
bool cmp1(point a,point b){
if(a.y!=b.y)return a.y<b.y;
return a.x<b.x;
}
bool cmp2(point a,point b){
if(a.x!=b.x)return a.x<b.x;
return a.y<b.y;
}
int n,X[M<<1],Y[M<<1],cnt1,cnt2,ltot,T[M];
int lowbit(int x){return x&(-x);}
void add(int x,int y){
for(;x<=cnt1;x+=lowbit(x))T[x]+=y;
}
int prefix(int x){
int ans=0;
for(;x;x-=lowbit(x))ans+=T[x];
return ans;
}
int main(){
n=read();
for(int i=1;i<=n;++i)P[i].x=X[i]=read(),P[i].y=Y[i]=read();
//离散化
std::sort(X+1,X+n+1);
std::sort(Y+1,Y+n+1);
cnt1=std::unique(X+1,X+n+1)-X-1;
cnt2=std::unique(Y+1,Y+n+1)-Y-1;
for(int i=1;i<=n;++i){
P[i].x=std::lower_bound(X+1,X+cnt1+1,P[i].x)-X;
P[i].y=std::lower_bound(Y+1,Y+cnt2+1,P[i].y)-Y;
}
//处理出所有横向的线段
//注意：这里只处理相邻的点，以防算重
std::sort(P+1,P+n+1,cmp1);
for(int i=1;i<n;++i)if(P[i].y==P[i+1].y)L[++ltot]=(line){P[i].x,P[i+1].x,P[i].y,0};
//处理出所有纵向的线段
std::sort(P+1,P+n+1,cmp2);
for(int i=1;i<n;++i)if(P[i].x==P[i+1].x){
L[++ltot]=(line){P[i].x,0,P[i].y,1};
L[++ltot]=(line){P[i].x,0,P[i+1].y,-1};
}
//扫描线
std::sort(L+1,L+ltot+1);
int ans=0;
for(int i=1;i<=ltot;++i){
if(L[i].w)add(L[i].l,L[i].w);
else ans+=prefix(L[i].r-1)-prefix(L[i].l);
}
printf("%d\n",ans+n);//注意：答案包括原有黑点
return 0;
}
原文地址：http://www.cnblogs.com/pokefunc/p/16860927.html
