内部白点
题意
无限大正方形网格里有n个黑色的顶点，所有其他顶点都是白色的（网格的顶点即坐标为整数的点，又称整点）。每秒钟，所有内部白点同时变黑，直到不存在内部白点为止。
你的任务是统计最后网格中的黑点个数。 内部白点的定义：一个白色的整点P(x,y)是内部白点当且仅当P在水平线的左边和右边各至少有一个黑点（即存在x1 < x < x2使得(x1,y)和(x2,y)都是黑点），且在竖直线的上边和下边各至少有一个黑点（即存在y1 < y < y2使得(x,y1)和(x,y2)都是黑点）。如果变色过程永不终止，输出-1。
（由于原本题意就很简明，所以我就不简述了）
Solution
显然不可能永不终止，因为白点变成黑点当且仅当白点在两条黑点线的交点上，也就是在黑点线上，这样以来黑点线的数量是不会变的。
所以考虑线离散化一遍坐标，然后树状数组差分维护一下，类似于扫描线的过程。
首先我们把全部与x轴垂直的线段找出来，然后我们找与y轴垂直的线段，在这个线段的左端点打上1的标记，右端点打上-1的标记，按照x坐标扫过去，遇见这些点我们就修改一下树状数组，然后一个线段就区间查询就好了。树状数组某一位代表的是y坐标，遇到右端点时线段在修改后就相当于被去掉了。
#include<bits/stdc++.h>
using namespace std;
inline int lowbit(int x){return x&-x;}
int c[200010];
int n;
void update(int x,int v){
while(x<=n){
c[x]+=v;
x+=lowbit(x);
}
}
int query(int x){
int ans=0;
while(x){
ans+=c[x];
x-=lowbit(x);
}
return ans;
}
struct node{
int x,y;
}a[200010];
bool cmp1(node a,node b){
return a.x==b.x?(a.y<b.y):a.x<b.x;
}
bool cmp2(node a,node b){
return a.y==b.y?(a.x<b.x):a.y<b.y;
}
int xxx[200010],yyy[200010];
int cnt1,cnt2;
map<int,int>mp1,mp2;
struct xline{
int l,r;
int x;
}l1[200010];
int tot1;
struct point{
int x,y;
int type;
}p[200010];
int tot2;
bool cmp(point a,point b){
return a.x==b.x?(a.y<b.y):a.x<b.x;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d%d",&a[i].x,&a[i].y);
xxx[i]=a[i].x,yyy[i]=a[i].y;
}
sort(xxx+1,xxx+1+n);
sort(yyy+1,yyy+1+n);
for(int i=1;i<=n;++i){
if(mp1[xxx[i]]==0)mp1[xxx[i]]=++cnt1;
if(mp2[yyy[i]]==0)mp2[yyy[i]]=++cnt2;
}
for(int i=1;i<=n;++i){
a[i].x=mp1[a[i].x];
a[i].y=mp2[a[i].y];
}
sort(a+1,a+1+n,cmp1);
for(int i=1;i<n;++i){
if(a[i].x==a[i+1].x){
l1[++tot1].x=a[i].x;
l1[tot1].l=a[i].y;
l1[tot1].r=a[i+1].y;
}
}
sort(a+1,a+1+n,cmp2);
for(int i=1;i<n;++i){
if(a[i].y==a[i+1].y){
p[++tot2].x=a[i].x,p[tot2].y=a[i].y,p[tot2].type=1;
p[++tot2].x=a[i+1].x,p[tot2].y=a[i+1].y,p[tot2].type=-1;
}
}
int ans=0;
int ttt=1;
sort(p+1,p+1+tot2,cmp);
for(int i=1;i<=tot1;++i){
if(l1[i].x!=l1[i-1].x)
for(int j=l1[i-1].x;j<=l1[i].x;++j){
while(j==p[ttt].x){
update(p[ttt].y,p[ttt].type);
++ttt;
}
}
ans+=(query(l1[i].r-1)-query(l1[i].l));
}
printf("%d
",ans+n);
}