[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，那么答案+1

用树状数组维护这个区间内满足条件的点数

令$l_i$为纵坐标为i，左边有多少点，$r_i$类似

如果$l[y]=0$那么y之后就可以构成一个答案+1

如果$r[y]=1$那么y之后就不再构成答案-1

然后区间求和[a[i-1].y+1,a[i].y-1](黑点不能变成黑点)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 typedef long long lol;
 8 struct ZYYS
 9 {
10   int x,y;
11 }a[800001];
12 int t[800001],num,l[800001],r[800001],n;
13 lol c[800001],ans;
14 bool cmp(ZYYS a,ZYYS b)
15 {
16   if (a.x==b.x) return a.y<b.y;
17   return a.x<b.x;
18 }
19 void update(int x,lol y)
20 {
21   while (x<=num)
22     {
23       c[x]+=y;
24       x+=(x&(-x));
25     }
26 }
27 lol query(int x)
28 {
29   lol s=0;
30   while (x)
31     {
32       s+=c[x];
33       x-=(x&(-x));
34     }
35   return s;
36 }
37 int main()
38 {int i,ed,j;
39   cin>>n;
40   for (i=1;i<=n;i++)
41     {
42       scanf("%d%d",&a[i].x,&a[i].y);
43       t[++num]=a[i].x;t[++num]=a[i].y;
44     }
45   sort(t+1,t+num+1);
46   num=unique(t+1,t+num+1)-t-1;
47   for (i=1;i<=n;i++)
48     {
49       a[i].x=lower_bound(t+1,t+num+1,a[i].x)-t;
50       a[i].y=lower_bound(t+1,t+num+1,a[i].y)-t;
51     }
52   sort(a+1,a+n+1,cmp);
53   for (i=1;i<=n;i++)
54     r[a[i].y]++;
55   ans=n;
56   for (i=1;i<=n;i=ed)
57     {
58       ed=i;
59       while (ed<=n&&a[ed].x==a[i].x) ed++;
60       for (j=i;j<ed;j++)
61     {
62       int y=a[j].y;
63       if (l[y]==0)
64         update(y,1);
65       if (r[y]==1)
66         update(y,-1);
67       l[y]++;r[y]--;
68       if (j>i&&j<ed)
69         ans+=query(y-1)-query(a[j-1].y);
70     }
71     }
72   cout<<ans<<endl;
73 }

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long lol;
struct ZYYS
{
int x,y;
}a[800001];
int t[800001],num,l[800001],r[800001],n;
lol c[800001],ans;
bool cmp(ZYYS a,ZYYS b)
{
if (a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
void update(int x,lol y)
{
while (x<=num)
    {
      c[x]+=y;
      x+=(x&(-x));
    }
}
lol query(int x)
{
lol s=0;
while (x)
    {
      s+=c[x];
      x-=(x&(-x));
    }
return s;
}
int main()
{int i,ed,j;
freopen("1818.in","r",stdin);
freopen("1818.out","w",stdout);
cin>>n;
for (i=1;i<=n;i++)
    {
      scanf("%d%d",&a[i].x,&a[i].y);
      t[++num]=a[i].x;t[++num]=a[i].y;
    }
sort(t+1,t+num+1);
num=unique(t+1,t+num+1)-t-1;
for (i=1;i<=n;i++)
    {
      a[i].x=lower_bound(t+1,t+num+1,a[i].x)-t;
      a[i].y=lower_bound(t+1,t+num+1,a[i].y)-t;
    }
sort(a+1,a+n+1,cmp);
for (i=1;i<=n;i++)
    r[a[i].y]++;
ans=n;
for (i=1;i<=n;i=ed)
    {
      ed=i;
      while (ed<=n&&a[ed].x==a[i].x) ed++;
      for (j=i;j<ed;j++)
   {
      int y=a[j].y;
      if (l[y]==0)
        update(y,1);
      if (r[y]==1)
        update(y,-1);
      l[y]++;r[y]--;
      if (j>i&&j<ed)
        ans+=query(y-1)-query(a[j-1].y);
   }
    }
cout<<ans<<endl;
}