P4121 [WC2005]双面棋盘

题目

P4121 [WC2005]双面棋盘

貌似是刘汝佳出的题目？？

做法

线段树维护并查集

线段树分治\(1\)~\(n\)行，我们要考虑维护的肯定是黑、白各自的联通块数量

考虑区间合并，其实就与中间这两层有关，\((n≤200)\)并查集暴力做一下就好了

My complete code

#include<cstdio>

#include<cstring>

#include<iostream>

#include<string>

#include<algorithm>

using namespace std;

typedef int LL;

const LL maxn=500;

inline LL Read(){

    LL x(0),f(1);char c=getchar();

    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();

    return x*f;

}

LL n,nod,root,m;

LL a[210][210],fa[maxn<<1],belong[maxn<<1];

struct Tree{

    LL f[maxn],son[2],sum[2];

}T[maxn<<1];

LL Get_fa(LL x){

    return fa[x]=(fa[x]==x?x:Get_fa(fa[x]));

}

inline void First(LL now,LL x){

    T[now].sum[a[x][1]]=1,

    T[now].sum[a[x][1]^1]=0;

    T[now].f[1]=T[now].f[1+n]=1;

    LL pre=1;

    for(LL i=2;i<=n;++i){

        if(a[x][i]!=a[x][pre])

            ++T[now].sum[a[x][pre=i]];

        T[now].f[i]=T[now].f[i+n]=pre;

    }

}

inline void Update(LL now,LL mid,LL lc,LL rc){

    for(LL i=0;i<2;++i)

        T[now].sum[i]=T[lc].sum[i]+T[rc].sum[i];

    for(LL i=1;i<=2*n;++i){

        fa[i]=T[lc].f[i],

        fa[i+2*n]=T[rc].f[i]+2*n;

    }

    for(LL i=1;i<=n;++i){

        LL fx(Get_fa(i+n)),fy(Get_fa(i+2*n));

        if(a[mid][i]==a[mid+1][i]&&fx!=fy){

            --T[now].sum[a[mid][i]];

            fa[fx]=fy;

        }

    }

    for(LL i=1;i<=n;++i){

        fa[i]=Get_fa(i);

        belong[fa[i]]=i;

    }

    for(LL i=n+1;i<=2*n;++i){

        fa[i+2*n]=Get_fa(i+2*n);

        belong[fa[i+2*n]]=i;

    }

    for(LL i=1;i<=n;++i){

        T[now].f[i]=belong[fa[i]];

        T[now].f[i+n]=belong[fa[i+3*n]];

    }

}

void Build(LL &now,LL l,LL r){

    now=++nod;

    if(l==r){

        First(now,l);

        return ;

    }

    LL mid(l+r>>1);

    Build(T[now].son[0],l,mid),Build(T[now].son[1],mid+1,r);

    Update(now,mid,T[now].son[0],T[now].son[1]);

}

void Change(LL now,LL l,LL r,LL c){

    if(l==r){

        First(now,l);

        return;

    }

    LL mid(l+r>>1);

    if(c<=mid)

        Change(T[now].son[0],l,mid,c);

    else

        Change(T[now].son[1],mid+1,r,c);

    Update(now,mid,T[now].son[0],T[now].son[1]);

}

int main(){

    n=Read();

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

        for(LL j=1;j<=n;++j)

            a[i][j]=Read();

    Build(root,1,n);

    m=Read();

    while(m--){

        LL x(Read()),y(Read());

        a[x][y]^=1;

        Change(root,1,n,x);

        printf("%d %d\n",T[root].sum[1],T[root].sum[0]);

    }

    return 0;

}

巴特西

P4121 [WC2005]双面棋盘

题目

做法

My complete code

最新文章

热门文章