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

先把所有点的\(x\)坐标离散化。

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

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

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

那么我们怎么维护交点呢？我们考虑用扫描线（如图黑线）。

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

然后从\(y\)坐标的小到大一个一个向上扫描，分3种情况讨论：

如果扫描到一条竖线的下端点\((x,y)\)，那么我们把树状数组里的位置\(x\)加\(1\)，即\(add(x,1)\)。
如果扫描到一条竖线的上端点\((x,y)\)，那么我们把树状数组里的位置\(x\)减\(1\)，即\(add(x,-1)\)。那么对于某一条竖线\(l\)，其上端点为\((x,y_1)\)，下端点为\((x,y_2)\)，我们就能保证当扫描线在区间\([y_1,y_2]\)时树状数组中位置\(x\)会\(+1\)。
如果扫描到一条横线，且两端点横坐标为\(x_1\)、\(x_2\)（\(x_1<x_2\)），我们只要查询\(query(x_2)-query(x_1-1)\)就可以得到这条线段上与其它竖线的交点坐标了，不过由于竖线与横线两端点的交点不能算进去，所以应该查询\(query(x_2-1)-query(x_1)\)。

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

代码如下：

#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】内部白点（树状数组+扫描线）

相关推荐