[WC2005]双面棋盘(并查集+分治)

题解

唉，还是码力不行，写了一个多小时发现想错了又重构了一个多小时。

这道题意图很显然，动态维护联通块，有一个经典做法就是用LCT维护按照删除时间维护的最大生成树。

网上还有一种神奇的做法，线段树套并查集，蒟蒻表示不懂。。

这道题可以利用并查集操作可以撤销这种性质来做。

线段树分治

线段树分治可以分两种情况，操作之间独立和操作之间不独立。

操作之间独立意味着我先完成哪个操作就可以，例如找最优点，有一道例题。

还有一种是操作之间是可以相互影响的，比如说这道题，连通性这种东西和我加的每一条边都有关。

我们可以按时间分治，先离线找出每条边出现的时间段，把这些时间段加入线段树中，然后在线段树上dfs，进入节点时把所有边加入，删除时栈序撤销来的时候的操作(因为线段树dfs的过程也是压栈弹栈的过程，所以我们可以准确撤销操作)，然后在根节点统计答案，联通块的个数为点数-边数，点数这种东西我们可以直接离线维护(我一开始傻了)。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<vector>

#define N 40002

#define maxn 209

using namespace std;

int n,id[maxn][maxn],f[N],tot,ls[N<<],rs[N<<],b[N],bl,w[N],wl,deep[N],num,last[N<<],m,root,a[maxn][maxn],bian;

int tag[maxn][maxn][],anti[],color[N<<];

const int dx[]={,,-,};

const int dy[]={,,,-};

inline int rd(){

    int x=;char c=getchar();bool f=;

    while(!isdigit(c)){if(c=='-')f=;c=getchar();}

    while(isdigit(c)){x=(x<<)+(x<<)+(c^);c=getchar();}

    return f?-x:x;

}

int find(int x){return f[x]==x?x:find(f[x]);}

struct node{int id,co;};

struct rbs{int dep,root,link,co;};

struct node2{int x,y;};

vector<node>vec[N<<];

vector<rbs>zh[N<<];

node2 linko[N<<];

void upd(int &cnt,int l,int r,int L,int R,int x,int y){

    if(!cnt)cnt=++tot;

    if(l>=L&&r<=R){vec[cnt].push_back(node{x,y});return;}

    int mid=(l+r)>>;

    if(mid>=L)upd(ls[cnt],l,mid,L,R,x,y);

    if(mid<R)upd(rs[cnt],mid+,r,L,R,x,y);

}

void solve(int &cnt,int l,int r){

    if(!cnt)cnt=++tot;

    //cout<<l<<"  ****  "<<r<<endl;

    for(int i=;i<vec[cnt].size();++i){

        int id=vec[cnt][i].id,co=vec[cnt][i].co;

        int x=linko[id].x,y=linko[id].y;

        int xx=find(x),yy=find(y);

        if(xx!=yy){

            if(co)bl++;else wl++;

            if(deep[xx]<deep[yy])swap(xx,yy);

            zh[cnt].push_back(rbs{deep[xx],xx,yy,co});

            f[yy]=xx;deep[xx]=max(deep[xx],deep[yy]+);

          }

    }

//    cout<<b[l]<<" "<<w[l]<<" "<<bl<<" "<<wl<<endl;

    if(l==r){if(l)printf("%d %d\n",b[l]-bl,w[l]-wl);}

    else{

    int mid=(l+r)>>;

    solve(ls[cnt],l,mid);

    solve(rs[cnt],mid+,r);

    }

    while(zh[cnt].size()){

        rbs x=zh[cnt].back();zh[cnt].pop_back();

        deep[x.root]=x.dep;f[x.link]=x.link;

        if(x.co)bl--;else wl--;

    }

}

int main(){

    anti[]=;anti[]=;anti[]=;anti[]=;

    n=rd();int x,y;

    for(int i=;i<=n;++i)

      for(int j=;j<=n;++j){

      a[i][j]=rd(),id[i][j]=++num;

      if(a[i][j])b[]++;else w[]++;

    }

    for(int i=;i<=num;++i)f[i]=i,deep[i]=;

    memset(last,-,sizeof(last));

    for(int i=;i<=n;++i)

      for(int j=;j<=n;++j)

          for(int k=;k<;++k){

              int xx=i+dx[k],yy=j+dy[k];

              if(!id[xx][yy])continue;

              tag[i][j][k]=tag[xx][yy][anti[k]]=++bian;

              if(a[i][j]==a[xx][yy])last[bian]=,color[bian]=a[i][j];

              linko[bian]=node2{id[i][j],id[xx][yy]};

          }

    m=rd();

    for(int i=;i<=m;++i){

        x=rd();y=rd();b[i]=b[i-];w[i]=w[i-];

        if(a[x][y])b[i]--,w[i]++;else b[i]++,w[i]--;

        for(int k=;k<;++k){

          int xx=x+dx[k],yy=y+dy[k],_id=tag[x][y][k];

          if(!_id)continue;

          if(a[x][y]==a[xx][yy])

            upd(root,,m,last[_id],i-,_id,a[x][y]),last[_id]=-;

          else last[_id]=i,color[_id]=a[xx][yy];

        }

        a[x][y]^=;

    }

    for(int i=;i<=n;++i)

      for(int j=;j<=n;++j)

        for(int k=;k<;++k){

          int xx=i+dx[k],yy=j+dy[k],_id=tag[i][j][k];

          if(~last[_id])upd(root,,m,last[_id],m,_id,color[_id]);

        }

    solve(root,,m);

    return ;

}

秒客网

[WC2005]双面棋盘(并查集+分治)

相关文章