bzoj1818 内部白点（好题）离散化+树状数组

　　题意：给出很多黑点，当一个坐标上下左右都有黑点时，这个点也被染成黑色，问最后黑点的数量。

　　思路：首先，一个很显然的结论，不可能出现无限染色的情况。所以不会输出-1，当n为0或者1时，答案就是0或者1.

　　　　其次，每一个新增的点其实就是横线和竖线的交点，我们先把所有的坐标都离散化，然后把横线和竖线都处理出来，分三类，横线，竖线的下端点，竖线的上端点，按照y从小到大排序。遇到竖线下端点时，树状数组x的位子加一，遇到上端点，x的位置减一，遇到横线，则是一段区间求和。

　　　　比较重要的端点问题和处理这三类点（线）的优先级问题，显然应该先删去，再求和，最后加上，所以在结构体中加入一个flag，既表示种类又表示优先级。区间求和的时候端点要注意。

　　　　我一开始将一条线上的所有点全部合并在同一条直线上，比如（1,1），（1,2），（1,3）直接合并成（1,1）到（1,3），这样处理首先很麻烦，其次会遇到某两条直线把（1,2）这个点染成黑色，重复计算的问题，所以只需要老老实实的分成很多线段就可以了。

#include<bits/stdc++.h>

#define CLR(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long ll;

const int maxn=;

struct node{

    ll x,y;

}a[maxn];

struct line{

    ll x1,y1,x2,y2;

    int flag;//1下端点  2横线  3代表上端点

}b[maxn<<];

bool cmpx(const node &u,const node &v)

{

    if(u.x==v.x)return u.y<v.y;

    return u.x<v.x;

}

bool cmpy(const node &u,const node &v)

{

    if(u.y==v.y)return u.x<v.x;

    return u.y<v.y;

}

bool cmpli(const line &u,const line &v){

    if(u.y1==v.y1)return u.flag>v.flag;

    return u.y1<v.y1;

}

ll hash1[maxn<<],hash2[maxn<<];

int n,h;

inline void Hash(){

    sort(hash1+,hash1++h);

    int m=;

    for(int i=;i<=h;i++)

    {

        if(i==||hash1[i]!=hash1[i-]){

            hash2[++m]=hash1[i];

        }

    }

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

    {

        a[i].x=lower_bound(hash2+,hash2++m,a[i].x)-hash2;

        a[i].y=lower_bound(hash2+,hash2++m,a[i].y)-hash2;

    }

}

ll c[maxn<<];

inline void add(int x,ll val)

{

    while(x<=)

    {

        c[x]+=val;

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

    }

}

inline ll getsum(int x)

{

    ll res=;

    while(x>)

    {

        res+=c[x];

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

    }

    return res;

}

int main(){

    cin>>n;

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

    {

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

        hash1[++h]=a[i].x,hash1[++h]=a[i].y;

    }

    if(n<=){

        printf("%d\n",n);

        return ;

    }

    Hash();

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

    ll xx=a[].x,yy=a[].y;

    int totline=;

    for(int i=;i<=n;i++)//竖线

    {

        if(a[i].x==xx)

        {

            b[totline].x1=xx;

            b[totline].y1=yy;

            b[totline].x2=a[i].x;

            b[totline].y2=a[i].y;

            xx=a[i].x;

             yy=a[i].y;

             totline++;

         }else{

             xx=a[i].x;

             yy=a[i].y;

               }

               if(i==n){

                   totline--;

               }

    }

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

    for(int i=;i<=totline;i++)

    {

        b[i].flag=;

        b[i+totline]=b[i];

        b[i+totline].flag=;

        b[i].x2=b[i].x1,b[i].y2=b[i].y1;

        b[i+totline].x1=b[i+totline ].x2,b[i+totline].y1=b[i+totline ].y2;

    }

    totline<<=;

    totline++;

    xx=a[].x,yy=a[].y;

    for(int i=;i<=n;i++)//竖线

    {

        if(a[i].y==yy)

        {

            b[totline].x1=xx;

            b[totline].y1=yy;

            b[totline].x2=a[i].x;

            b[totline].y2=a[i].y;

            b[totline].flag=;

            xx=a[i].x;

             yy=a[i].y;

             totline++;

         }else{

             xx=a[i].x;

             yy=a[i].y;

              }

              if(i==n)totline--;

    }

    sort(b+,b++totline,cmpli);

    //1下端点  2横线  3代表上端点

//    for(int i=1;i<=totline;i++)

//    {

//        printf("i:%d  flag:%d   x1:%d  y1:%d  x2:%d  y2:%d\n",i,b[i].flag,b[i].x1,b[i].y1,b[i].x2,b[i].y2);

//    }

    ll ans=;

    for(int i=;i<=totline;i++)

    {

        if(b[i].flag==){

            add(b[i].x1,);

        }else if(b[i].flag==){

            xx=b[i].x1,yy=b[i].x2;

            if(yy->=xx+){

                ans-=getsum(xx);

                ans+=getsum(yy-);

            }

        }else if(b[i].flag==){

            add(b[i].x1,-);

        }

    }

    printf("%lld\n",ans+n);

}

/*

10

6  7

3  8

5  2

6  4

1  5

5  4

1  10

8  7

1  8

4  10

9

2  4

4  1

8  4

7  1

7  10

1  10

6  4

6  8

6  1

*/

1818: [Cqoi2010]内部白点

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 1418 Solved: 635
[Submit][Status][Discuss]

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

巴特西

bzoj1818 内部白点（好题）离散化+树状数组

1818: [Cqoi2010]内部白点

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章

巴特西

bzoj1818 内部白点（好题） 离散化+树状数组

1818: [Cqoi2010]内部白点

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章

bzoj1818 内部白点（好题）离散化+树状数组