[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

数据范围
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](黑点不能变成黑点)

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 typedef long long lol;

 struct ZYYS

 {

   int x,y;

 }a[];

 int t[],num,l[],r[],n;

 lol c[],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=;

   while (x)

     {

       s+=c[x];

       x-=(x&(-x));

     }

   return s;

 }

 int main()

 {int i,ed,j;

   cin>>n;

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

     {

       scanf("%d%d",&a[i].x,&a[i].y);

       t[++num]=a[i].x;t[++num]=a[i].y;

     }

   sort(t+,t+num+);

   num=unique(t+,t+num+)-t-;

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

     {

       a[i].x=lower_bound(t+,t+num+,a[i].x)-t;

       a[i].y=lower_bound(t+,t+num+,a[i].y)-t;

     }

   sort(a+,a+n+,cmp);

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

     r[a[i].y]++;

   ans=n;

   for (i=;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]==)

         update(y,);

       if (r[y]==)

         update(y,-);

       l[y]++;r[y]--;

       if (j>i&&j<ed)

         ans+=query(y-)-query(a[j-].y);

     }

     }

   cout<<ans<<endl;

 }

#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;
}

秒客网