POJ 2109 Inner Vertices（扫描线+树状数组）

【题目大意】

　　在一个棋盘上放满白子，现在把一些白子变成黑子，
　　如果一个白子上下左右都有黑子，就会变成黑子，问最终黑子个数

【题解】

　　首先我们在每列的开头和结尾做标记，之后对行线扫描，
　　如果是列的开头，那么在该列中标记，如果是列的结尾，则在该列中去除标记
　　那么我们只要统计行的开头到行的结尾之间夹着多少列标记，且该列下该行没有原来的黑子
　　就是该行新增的黑子数量，对于总的黑子数量，可以用树状数组统计，之后容斥一下列标记即可。

【代码】

#include <cstdio>

#include <algorithm>

#include <utility>

#define cx first

#define cy second

using namespace std;

typedef long long LL;

const int MAX_N=100010;

typedef pair<int,int> P;

int t,c[MAX_N],r[MAX_N],N,ys[MAX_N],d[MAX_N],vis[MAX_N];

P p[MAX_N];

bool cmp(int a,int b){return p[a].cy<p[b].cy||p[a].cy==p[b].cy&&p[a].cx<p[b].cx;}

int sum(int x){int s=0;while(x)s+=c[x],x-=(x&-x);return s;}

void add(int x,int v){while(x<=t)c[x]+=v,x+=x&-x;}

int main(){

    scanf("%d",&N);

    for(int i=0;i<N;i++)scanf("%d%d",&p[i].cx,&p[i].cy),r[i]=i;

    sort(p,p+N); sort(r,r+N,cmp);

    ys[r[0]]=1; d[r[0]]=1;

    for(int i=1;i<N;i++){

        ys[r[i]]=ys[r[i-1]];

        if(p[r[i]].cy==p[r[i-1]].cy)continue;

        d[r[i-1]]--; d[r[i]]++;

        ys[r[i]]++;

    }LL ans=N; d[r[N-1]]--; t=ys[r[N-1]];

    for(int i=0,j=0;i<N;){

        for(j=i;j<N&&p[j].cx==p[i].cx;j++)

            if(d[j]<0){vis[ys[j]]=0;add(ys[j],-1);}

        if(ys[i]<ys[j-1]-1){

            ans+=sum(ys[j-1]-1)-sum(ys[i]);

            for(int k=i+1;k<j-1;k++)if(vis[ys[k]])ans--;

        }for(;i<j;i++)if(d[i]>0){add(ys[i],1);vis[ys[i]]=1;}

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

    return 0;

}

巴特西

POJ 2109 Inner Vertices（扫描线+树状数组）

最新文章

热门文章