[Wc]Dface双面棋盘（）

题解：

一道维护奇怪信息的线段树。。。

我刚开始看了标签想的是删去图上一个点后求连通性

发现不会

于是退化成一般图支持删除插入维护连通性

发现有2两种做法

1.lct维护

按照结束顺序先后排序，给每条边一个权值

然后我们只要维护最大生成树就好了，因为这样可以保证删除当前树上的边是不会被权值更小的边替换的

而由于最大生成树的性质，是不可能能替换成更大的边的

so这说明删除它之后就不需要连边了

nlogn^2但是常数大吧

2.线段树分治

这个应该很明显吧，变成只有插入的并查集问题

nlogn^2logn^2 本来常数不大但是自带了4

写代码：1h

debug：30min

#pragma G++ optimize (2)

#include <bits/stdc++.h>

using namespace std;

#define IL inline

#define rint register int

char ss[<<],*A=ss,*B=ss;

IL char gc(){return A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++;}

template<class T>void read(T&x){

    rint f=,c;while(c=gc(),c<||<c)if(c=='-')f=-;x=c^;

    while(c=gc(),<c&&c<)x=(x<<)+(x<<)+(c^);x*=f;

}

char sr[<<],z[];int C=-,Z;

template<class T>void wer(T x){

    if(x<)sr[++C]='-',x=-x;

    while(z[++Z]=x%+,x/=);

    while(sr[++C]=z[Z],--Z);sr[++C]=' ';

}

const int N=;

const int N2=1e4+1e3;

int a[N][N],f1[N][N][],f0[N][N][],n,m;

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

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

int pos[]={,,,,};

IL bool pd(int x,int y)

{

  if (<=x&&x<=n&&<=y&&y<=n) return();

  else return();

}

struct re{

  int a,b,c;

};

IL int js(int x,int y)

{

  return(x*n+y);

}

struct sgt

{

  vector<re> ve[N2*];

  int fa[N*N],count2[N*N],ans[N2];

  sgt() { for (int i=;i<=N*N-;i++) fa[i]=i,count2[i]=;}

  #define mid ((h+t)>>1)

  void insert(int x,int h,int t,int h1,int t1,re k)

  {

    if (h1>t1) return;

    if (h1<=h&&t<=t1)

    {

      ve[x].push_back(k); return;

    }

    if (h1<=mid) insert(x*,h,mid,h1,t1,k);

    if (mid<t1) insert(x*+,mid+,t,h1,t1,k);

  }

  IL int find(int &x)

  {

    while (fa[x]!=x) x=fa[x];

  }

  void dfs(int x,int h,int t,int cnt)

  {

   // cout<<x<<" "<<h<<" "<<t<<endl;

    stack<re> s;

    int cnt2=cnt;

    for (rint i=;i<ve[x].size();i++)

    {

      re t=ve[x][i];

      rint x1=js(t.a,t.b),x2=js(t.a+dx[t.c],t.b+dy[t.c]);

      find(x1); find(x2);

      if (x1!=x2)

      {

        if (count2[x1]>count2[x2]) swap(x1,x2);

        cnt2++;

        s.push((re){x1,x2,count2[x2]});

        fa[x1]=x2; count2[x2]+=count2[x1];

      }

    }

    if (h==t) ans[h]=cnt2;

    else

    {

      dfs(x*,h,mid,cnt2);

      dfs(x*+,mid+,t,cnt2);

    }

    while (!s.empty())

    {

      re t=s.top(); s.pop();

      fa[t.a]=t.a; count2[t.b]=t.c;

    }

  }

}se1,se0;

int main()

{

  freopen("1.in","r",stdin);

  freopen("1.out","w",stdout);

  read(n);

  int ans[][N2]={};

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

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

    {

      read(a[i][j]);

      ans[a[i][j]][]++;

    }

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

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

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

        f1[i][j][k]=-,f0[i][j][k]=-;

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

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

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

        if (pd(i+dx[k],j+dy[k])&&a[i][j]==a[i+dx[k]][j+dy[k]])

          if (a[i][j]) f1[i][j][k]=;

          else f0[i][j][k]=;

  read(m);

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

  {

    int x,y;

    read(x); read(y);

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

      if (pd(x+dx[k],y+dy[k]))

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

        {

          if (a[x+dx[k]][y+dy[k]]==a[x][y])

            se1.insert(,,m,max(f1[x][y][k],),i-,(re){x,y,k}),

            f1[x][y][k]=-,f1[x+dx[k]][y+dy[k]][pos[k]]=-;

          else

            f0[x][y][k]=i,f0[x+dx[k]][y+dy[k]][pos[k]]=i;

        }

        else

          if (a[x+dx[k]][y+dy[k]]==a[x][y])

            se0.insert(,,m,max(f0[x][y][k],),i-,(re){x,y,k}),

            f0[x][y][k]=-,f0[x+dx[k]][y+dy[k]][pos[k]]=-;

          else

            f1[x][y][k]=i,f1[x+dx[k]][y+dy[k]][pos[k]]=i;

    if(a[x][y]==) ans[][i]=ans[][i-]+,ans[][i]=ans[][i-]-;

    else ans[][i]=ans[][i-]+,ans[][i]=ans[][i-]-;

    a[x][y]^=;

  }

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

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

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

      {

        if (f1[i][j][k]>=)

        {

          se1.insert(,,m,max(,f1[i][j][k]),m,(re){i,j,k});

        }

        if (f0[i][j][k]>=)

        {

          se0.insert(,,m,max(,f0[i][j][k]),m,(re){i,j,k});

        }

      }

/*  for (int i=1;i<=1;i++)

    for (int j=0;j<se1.ve[i].size();j++)

      cout<<se1.ve[1][j].a<<" "<<se1.ve[1][j].b<<" "<<se1.ve[1][j].c<<endl;

  cout<<endl; */

  se1.dfs(,,m,);

  se0.dfs(,,m,);

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

    wer(ans[][i]-se1.ans[i]),wer(ans[][i]-se0.ans[i]),sr[++C]='\n';

  fwrite(sr,,C+,stdout);

  // changshi fen ge fu

  return ;

}

然后由于这个牵扯出loj122这题维护动态图连通性

并没有看懂网上的唯一一篇题解于是弃疗

正解：

线段树上的每个叶子节点表示一行

每个节点维护当前范围内的黑白区间个数

合并的时候就用并查集启发式合并就可以

每次合并是o（n）的

每次修改进行log次

所以复杂度应该是O(nmlogn)

相比上面两种都不优吧但是常数小了至少2倍因为这个是单点修改上面的要修改4条边

写完我发现我这种写法极其冗长

由于0,1完全等价

完全可以把它们弄成结构题然后修改做两次这样代码就可以短大约一半低于普遍长度了

写代码：1h+

调试：40min

数据结构的代码能力很需要提升啊

如果这题能做到30min写完20min调完我觉得那就能很强了

不过这个时间我觉得写得常数可能非常大

经过优化的线段树分治只用了0.3s不到（本地）

这个用了2.4s

主要消耗时间的无疑是updata这里

我写得时候想的是先将两个儿子合并在一起，然后再搞

然后我就合并了4*n

其实只要中间的2*n就可以了，这样常数是2

另外我刚开始统计联通块数目用的是一个很傻比的方法

里面的一些信息没删可能也导致了时间的增加

于是我决定再去卡一波常数

这个是源代码：

#pragma G++ optimize (2)

#include <bits/stdc++.h>

using namespace std;

#define IL inline

#define rint register int

char ss[<<],*A=ss,*B=ss;

IL char gc(){return A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++;}

template<class T>void read(T&x){

    rint f=,c;while(c=gc(),c<||<c)if(c=='-')f=-;x=c^;

    while(c=gc(),<c&&c<)x=(x<<)+(x<<)+(c^);x*=f;

}

char sr[<<],z[];int C=-,Z;

template<class T>void wer(T x){

    if(x<)sr[++C]='-',x=-x;

    while(z[++Z]=x%+,x/=);

    while(sr[++C]=z[Z],--Z);sr[++C]=' ';

}

const int N=;

const int N2=1e4+1e3;

int a[N][N],n,m,ph[N*],pt[N*];

struct bcj{

  int fa[N*][N*],data[N*];

  int find(int x,int y)

  {

    int ans;

    if (fa[x][y]!=y) ans=find(x,fa[x][y]);

    else return(y);

    fa[x][y]=ans;

    return(ans);

  }

}b1,b2;

struct mn{

  int fa[N*],pos[N*];

  bool f[N*];

  int find(int x)

  {

    int ans;

    if (fa[x]!=x) ans=find(fa[x]);

    else return(x);

    fa[x]=ans;

    return(ans);

  }

}c1,c2;

IL bool pd(int x)

{

  if ((<=x&&x<=n)||(*n<x&&x<=*n)) return();

  else return();

}

IL int mex(int x,int y)

{

  if (y==) return();

  else return(x+y);

}

void updata(int x)

{

  int h1=ph[x*],t1=pt[x*],h2=ph[x*+],t2=pt[x*+];

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

    c1.fa[i]=b1.fa[x*][i],c2.fa[i]=b2.fa[x*][i];

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

    c1.fa[i+*n]=mex(*n,b1.fa[x*+][i]),

    c2.fa[i+*n]=mex(*n,b2.fa[x*+][i]);

  int cnt1=,cnt2=;

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

    if (a[t1][i]==a[h2][i])

      if (a[t1][i])

      {

        int x1=c1.find(n+i);

        int x2=c1.find(*n+i);

        if (x1!=x2&&x1!=&&x2!=) c1.fa[x1]=x2,cnt1++;

      } else

      {

        int x1=c2.find(n+i);

        int x2=c2.find(*n+i);

        if (x1!=x2&&x1!=&&x2!=) c2.fa[x1]=x2,cnt2++;

      }

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

    c1.f[i]=c2.f[i]=c1.pos[i]=c2.pos[i]=;

  c1.f[]=c2.f[]=;

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

  {

    int x1=c1.find(i);

    if (x1)

    if (pd(x1))

    {

      b1.fa[x][i]=x1;

      if(!c1.f[x1]) c1.f[x1]=;

    }

    else

      if (c1.pos[x1]) b1.fa[x][i]=c1.pos[x1];

      else b1.fa[x][i]=i,c1.pos[x1]=i;

    int x2=c2.find(i);

    if (x2)

    if (pd(x2))

    {

      b2.fa[x][i]=x2;

      if(!c2.f[x2]) c2.f[x2]=;

    }

    else

      if (c2.pos[x2]) b2.fa[x][i]=c2.pos[x2];

      else b2.fa[x][i]=i,c2.pos[x2]=i;

  }

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

  {

    int x1=c1.find(i);

    if (x1)

    if (pd(x1))

    {

      b1.fa[x][i-*n]=x1;

      if(!c1.f[x1]) c1.f[x1]=;

    }

    else

      if (c1.pos[x1]) b1.fa[x][i-*n]=c1.pos[x1];

      else b1.fa[x][i-*n]=i,c1.pos[x1]=i;

    int x2=c2.find(i);

    if (x2)

    if (pd(x2))

    {

      b2.fa[x][i-*n]=x2;

      if(!c2.f[x2]) c2.f[x2]=;

    }

    else

      if (c2.pos[x2]) b2.fa[x][i-*n]=c2.pos[x2];

      else b2.fa[x][i-*n]=i,c2.pos[x2]=i;

  }

  b1.data[x]=b1.data[x*]+b1.data[x*+]-cnt1;

  b2.data[x]=b2.data[x*]+b2.data[x*+]-cnt2;

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

  {

    if (b1.fa[x][i]>*n) b1.fa[x][i]-=*n;

    if (b2.fa[x][i]>*n) b2.fa[x][i]-=*n;

  }

}

#define mid ((h+t)/2)

void build(int x,int h,int t)

{

  ph[x]=h; pt[x]=t;

  if (h==t)

  {

    int cnt1=,cnt2=;

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

    if (a[h][i])

      b1.fa[x][i]=i,b2.fa[x][i]=,cnt1++;

    else

      b1.fa[x][i]=,b2.fa[x][i]=i,cnt2++;

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

      b1.fa[x][i]=b1.fa[x][i-n],b2.fa[x][i]=b2.fa[x][i-n];

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

      if (a[h][i]==a[h][i+])

        if (a[h][i])

        {

          int x1=b1.find(x,i);

          int x2=b1.find(x,i+);

          if (x1!=x2)

            b1.fa[x][x1]=x2,cnt1--;

        } else

        {

          int x1=b2.find(x,i);

          int x2=b2.find(x,i+);

          if (x1!=x2)

            b2.fa[x][x1]=x2,cnt2--;

        }

    b1.data[x]=cnt1;

    b2.data[x]=cnt2;

    return;

  }

  build(x*,h,mid); build(x*+,mid+,t);

  updata(x);

}

void change(int x,int h,int t,int pos,int k)

{

  if (h==t)

  {

    a[pos][k]^=;

    int cnt1=,cnt2=;

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

    if (a[h][i])

      b1.fa[x][i]=i,b2.fa[x][i]=,cnt1++;

    else

      b1.fa[x][i]=,b2.fa[x][i]=i,cnt2++;

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

      b1.fa[x][i]=b1.fa[x][i-n],b2.fa[x][i]=b2.fa[x][i-n];

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

      if (a[h][i]==a[h][i+])

        if (a[h][i])

        {

          int x1=b1.find(x,i);

          int x2=b1.find(x,i+);

          if (x1!=x2)

            b1.fa[x][x1]=x2,cnt1--;

        } else

        {

          int x1=b2.find(x,i);

          int x2=b2.find(x,i+);

          if (x1!=x2)

            b2.fa[x][x1]=x2,cnt2--;

        }

    b1.data[x]=cnt1;

    b2.data[x]=cnt2;

    return;

  }

  if (pos<=mid) change(x*,h,mid,pos,k);

  else change(x*+,mid+,t,pos,k);

  updata(x);

}

int main()

{

  freopen("1.in","r",stdin);

  freopen("1.out","w",stdout);

  read(n);

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

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

      read(a[i][j]);

  build(,,n);

 // cout<<b1.data[1]<<" "<<b2.data[1]<<endl;

  read(m);

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

  {

    int x,y;

    read(x); read(y);

    change(,,n,x,y);

    wer(b1.data[]);

    wer(b2.data[]);

    sr[++C]='\n';

  }

  fwrite(sr,,C+,stdout);

  return ;

}

巴特西

[Wc]Dface双面棋盘（）

最新文章

热门文章