题解：
一道维护奇怪信息的线段树。。。
我刚开始看了标签想的是删去图上一个点后求连通性
发现不会
于是退化成一般图支持删除 插入 维护连通性
发现有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 ;
}