[WC2005]双面棋盘 题解

· · 题解

赛后写题解补教训

场上数组开小本机AC但开了O2就会RE=爆零

洛谷上测由于数组开小导致访问不到死递归MLE我还以为还是开大了

小心，小心，再小心

我们尝试建立一棵线段树。

线段树的每一个叶子节点是一行，每一个节点是一段行。

每一个节点存上两个东西：

对于单独的每一行，我们搞一个并查集：如果在这一行中，i\dots j 的颜色相同，那么我们把 i\dots j 都放到同一个集合中。用最小表示法，这个集合的代表就是最小的元素 i。

我们考虑合并两个行区间。

显然，新的行区间的上并查集就是左儿子的上并查集，新区间的下并查集就是右儿子的下并查集。

考虑左儿子的下并查集与右儿子的上并查集结合所带来的贡献。

首先令新节点的颜色 c 的连通块数等于其两个儿子的该颜色的连通块数之和。

然后枚举，对于第 i 列，如果 gird_{md,i} = gird_{md+1,i}，那么显然这两个在同一个连通块中，要将该颜色的数量-1。

然后写个标准的线段树就完事了~

总时间复杂度 O(能过) O(n^2+mnlogn)

Code:

#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define int short
using namespace std;
const int mxn=808;
int gird[mxn][mxn],n,m,q;
    struct dsu{
        int fa[mxn<<1];
        inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
        inline void uni(int x,int y){
            x=find(x),y=find(y);
            fa[x]=y;
        }
        inline void init(){for(int i=1;i<(mxn<<1);++i)fa[i]=i;}
    }f;
    int stand[mxn];
    struct node{
        dsu d;
        int son[2],ans[2];
        inline void init(){
            ans[0]=0,ans[1]=0;d.init();
            son[0]=0,son[1]=0;
        }
    }t[mxn<<1];
    inline void ForceUpdate(int id,int x){
        t[id].init();
        t[id].ans[gird[x][1]]=1;
        t[id].ans[1-gird[x][1]]=0;
        int pre=1;
        for(int i=1;i<=m;++i){
            if(gird[x][i]!=gird[x][pre]){
                ++t[id].ans[gird[x][i]];
                pre=i;
            }
            t[id].d.uni(i,pre),t[id].d.uni(i+n,pre);
        }
    }
    inline void pushup(int id,int md,int l,int r){
        f.init();
        for(int i=0;i<2;++i)t[id].ans[i]=t[l].ans[i]+t[r].ans[i];
        for(int i=1;i<=m*2;++i)f.fa[i]=t[l].d.fa[i],f.fa[i+m*2]=t[r].d.fa[i]+m*2;
        for(int i=1;i<=m;++i){
            int fx=f.find(i+m),fy=f.find(i+2*m);
            if(gird[md][i]==gird[md+1][i] and fx!=fy){
                --t[id].ans[gird[md][i]];
                f.uni(fx,fy);
            }
        }
        memset(stand,0,sizeof(stand));     // stand 数组的用处是最小表示
        for(int i=m;i;--i){
            f.fa[i]=f.find(i);
            stand[f.fa[i]]=i;
        }
        for(int i=m*2;i>m;--i){
            f.fa[i+m*2]=f.find(i+m*2);
            stand[f.fa[i+m*2]]=i;
        }
        for(int i=1;i<=m;++i){
            t[id].d.fa[i]=stand[f.fa[i]];
            t[id].d.fa[i+m]=stand[f.fa[i+m*3]];
        }
    }
    int cntnode=0,root;
    inline void build(int&id,int l,int r){
        id=++cntnode;
        if(l==r){
            ForceUpdate(id,l);
            return;
        }
        int md=l+r>>1;
        build(t[id].son[0],l,md);
        build(t[id].son[1],md+1,r);
        pushup(id,md,t[id].son[0],t[id].son[1]);
    }
    inline void upd(int id,int l,int r,int x){
        if(l==r){
            ForceUpdate(id,x);
            return;
        }
        int md=l+r>>1;
        if(x<=md)upd(t[id].son[0],l,md,x);
        else upd(t[id].son[1],md+1,r,x);
        pushup(id,md,t[id].son[0],t[id].son[1]);
    }
    inline void glhf(){
        build(root,1,n);
        for(;q--;){
            int x,y;
            cin>>x>>y;
            gird[x][y]^=1;
            upd(root,1,n,x);
            cout<<t[root].ans[1]<<' '<<t[root].ans[0]<<'\n';
        }
    }
inline void solve(){
    cin>>n;m=n;
    for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)cin>>gird[i][j];
    cin>>q;
    glhf();
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T;T=1;
//  cin>>T;
    for(;T--;)solve();
    return 0;
}