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

正解：扫描线+树状数组。

容易发现，如果一个白点的上下左右都有黑点，那么它就能变成白点。

所以点是可以直接离散化的，无数点的情况也是没有的。

于是直接写一个扫描线，扫描每一列，然后用树状数组统计每一行是否上下都有黑点就行了。

 1 #include <bits/stdc++.h>
 2 #define il inline
 3 #define RG register
 4 #define ll long long
 5 #define lb(x) (x & -x)
 6 #define inf (1<<30)
 7 #define N (100005)
 8 
 9 using namespace std;
10 
11 struct point{ int x,y; }p[N];
12 
13 vector<int> g[N];
14 int hsh[N],num[N],cnt[N],can[N],c[N],mn[N],mx[N],n,tot;
15 ll ans;
16 
17 il int gi(){
18   RG int x=0,q=1; RG char ch=getchar();
19   while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
20   if (ch=='-') q=-1,ch=getchar();
21   while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
22   return q*x;
23 }
24 
25 il void add(RG int x,RG int v){
26   for (;x<=n;x+=lb(x)) c[x]+=v; return;
27 }
28 
29 il int query(RG int x){
30   RG int res=0;
31   for (;x;x^=lb(x)) res+=c[x]; return res;
32 }
33 
34 int main(){
35 #ifndef ONLINE_JUDGE
36   freopen("white.in","r",stdin);
37   freopen("white.out","w",stdout);
38 #endif
39   n=gi();
40   for (RG int i=1;i<=n;++i) hsh[++tot]=p[i].x=gi(),p[i].y=gi();
41   sort(hsh+1,hsh+tot+1),tot=unique(hsh+1,hsh+tot+1)-hsh-1;
42   for (RG int i=1;i<=n;++i) p[i].x=lower_bound(hsh+1,hsh+tot+1,p[i].x)-hsh;
43   for (RG int i=1;i<=n;++i) mn[i]=inf,mx[i]=0;
44   tot=0; for (RG int i=1;i<=n;++i) hsh[++tot]=p[i].y;
45   sort(hsh+1,hsh+tot+1),tot=unique(hsh+1,hsh+tot+1)-hsh-1;
46   for (RG int i=1;i<=n;++i) p[i].y=lower_bound(hsh+1,hsh+tot+1,p[i].y)-hsh;
47   for (RG int i=1;i<=n;++i){
48     g[p[i].x].push_back(i),++cnt[p[i].y];
49     mn[p[i].x]=min(mn[p[i].x],p[i].y),mx[p[i].x]=max(mx[p[i].x],p[i].y);
50   }
51   for (RG int i=1;i<=n;++i){
52     if (mn[i]>mx[i]) continue;
53     for (RG int j=0,k;j<g[i].size();++j){
54       k=p[g[i][j]].y,++num[k];
55       if (can[k]!=(num[k]&&cnt[k])) add(k,1),can[k]=1;
56     }
57     if (mn[i]!=mx[i]) ans+=query(mx[i]-1)-query(mn[i])+2; else ++ans;
58     for (RG int j=0,k;j<g[i].size();++j){
59       k=p[g[i][j]].y,--cnt[k];
60       if (can[k]!=(num[k]&&cnt[k])) add(k,-1),can[k]=0;
61     }
62   }
63   cout<<ans; return 0;
64 }