【BZOJ1818】【CQOI2010】【XSY2428】内部白点(树状数组+扫描线

作者:神秘网友 发布时间:2020-10-03 07:00:53

【BZOJ1818】【CQOI2010】【XSY2428】内部白点(树状数组+扫描线

【BZOJ1818】【CQOI2010】【XSY2428】内部白点(树状数组+扫描线)

先把所有点的xxx坐标离散化。

然后分别将所有点按xxx、yyy排序。这里以按xxx排序为例,对于xxx坐标相同的两个点,我们把它们连成一条线段。那么按yyy坐标排序也一样,把yyy坐标相同的两个点也连成一条线段。

那么连出来后的图就是这样的:

【BZOJ1818】【CQOI2010】【XSY2428】内部白点(树状数组+扫描线

那么横竖线段的所有交点(图中蓝点)即为可以变dark的点,因为它左右有dark点,上下都有dark点,符合变dark条件。

那么我们怎么维护交点呢?我们考虑用扫描线(如图黑线)。

我们先把横线、竖线的两个端点全部塞进一个数组里,然后把它们按yyy坐标排序。

然后从yyy坐标的小到大一个一个向上扫描,分3种情况讨论:

  1. 如果扫描到一条竖线的下端点(x,y)(x,y)(x,y),那么我们把树状数组里的位置xxx加111,即add(x,1)add(x,1)add(x,1)。

  2. 如果扫描到一条竖线的上端点(x,y)(x,y)(x,y),那么我们把树状数组里的位置xxx减111,即add(x,?1)add(x,-1)add(x,?1)。那么对于某一条竖线lll,其上端点为(x,y1)(x,y_1)(x,y1?),下端点为(x,y2)(x,y_2)(x,y2?),我们就能保证当扫描线在区间[y1,y2][y_1,y_2][y1?,y2?]时树状数组中位置xxx会+1+1+1。

  3. 如果扫描到一条横线,且两端点横坐标为x1x_1x1?、x2x_2x2?(x1<x2x_1<x_2x1?<x2?),我们只要查询query(x2)?query(x1?1)query(x_2)-query(x_1-1)query(x2?)?query(x1??1)就可以得到这条线段上与其它竖线的交点坐标了,不过由于竖线与横线两端点的交点不能算进去,所以应该查询query(x2?1)?query(x1)query(x_2-1)-query(x_1)query(x2??1)?query(x1?)。

那么最后答案就是所有交点的个数了。

代码如下:

#include<bits/stdc++.h>
 
#define N 100010
 
using namespace std;
 
struct Point
{
    int x,y;
}p[N];
 
struct Line 
{
    int opt,x,r,y;//1 竖线下端点 0 横线 -1 竖线上端点
}l[N*10];
 
int n,ans,cnt,b[N],c[N];
 
 //树状数组
int lowbit(int x)
{
    return x&-x;
}
 
void add(int x,int y)
{
    for(;x<=n;x+=lowbit(x))c[x]+=y;
}
 
int query(int x)
{
    int ans=0;
    for(;x;x-=lowbit(x))ans+=c[x];
    return ans;
}
 
bool cmpx(Point a,Point b){return a.x==b.x?a.y<b.y:a.x<b.x;}
bool cmpy(Point a,Point b){return a.y==b.y?a.x<b.x:a.y<b.y;}
bool cmpLine(Line a,Line b){return a.y==b.y?a.opt<b.opt:a.y<b.y;}
 
void work()
{
    sort(p+1,p+n+1,cmpx);
    for(int i=1;i<n;i++)
    {
        if(p[i].x==p[i+1].x)
        {
            l[++cnt]=(Line){1,p[i].x,0,p[i].y};
            l[++cnt]=(Line){-1,p[i].x,0,p[i+1].y};
        }
    }
    sort(p+1,p+n+1,cmpy);
    for(int i=1;i<n;i++)
        if(p[i].y==p[i+1].y)
            l[++cnt]=(Line){0,p[i].x,p[i+1].x,p[i].y};
}
 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&p[i].x,&p[i].y);
        b[i]=p[i].x;
    }   
    sort(b+1,b+n+1);//离散化
    int tot=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++)
        p[i].x=lower_bound(b+1,b+tot+1,p[i].x)-b;
  	work();//加入线段
    sort(l+1,l+cnt+1,cmpLine);//扫描
    for(int i=1;i<=cnt;i++)
    {
        if(!l[i].opt)ans+=query(l[i].r-1)-query(l[i].x);
        else add(l[i].x,l[i].opt);
    }
    printf("%d\n",ans+n);
    return 0;
}

【BZOJ1818】【CQOI2010】【XSY2428】内部白点(树状数组+扫描线相关教程