就是有这样一份代码,它用来输出调试的语句已经比代码长了(((
我人要麻了,就写的是 线段树+并查集,但是就是错了
dalao们帮忙调一下吧,球球了!蒟蒻已经调了4天了QAQ
有不知所云的地方随时问我,我全天 16+ 小时在线……
已经调崩了一个老师和两个同学了(默哀)
#include<bits/stdc++.h>
using namespace std;
int n,m;
bool t[205][205];
struct node{
int x,y;
}a[205][205];
bool operator==(node A,node B){return (A.x==B.x&&A.y==B.y);}
bool operator!=(node A,node B){return (A.x!=B.x||A.y!=B.y);}
node BOSS(node A){return a[A.x][A.y]=(a[A.x][A.y]==A?A:BOSS(a[A.x][A.y]));}
void HB(node A,node B){a[BOSS(A).x][BOSS(A).y]=BOSS(B);}
struct nnode{
int l,r,num_b,num_w;
node bup[205],bdn[205];
}tr[10005];
void cll(int now,int x)
{
for(int i=1;i<=n;i++) a[x][i]={x,i};
tr[now].num_b=tr[now].num_w=0;
if(t[x][1]) tr[now].num_b++;
else tr[now].num_w++;
for(int i=2;i<=n;i++)
{
if(t[x][i]!=t[x][i-1])
{
if(t[x][i]) tr[now].num_b++;
else tr[now].num_w++;
}
else HB({x,i},{x,i-1});
}
for(int i=1;i<=n;i++) tr[now].bup[i]=tr[now].bdn[i]=BOSS({x,i});
// cout<<"////////////////////////"<<tr[now].num_b<<" "<<tr[now].num_w<<'\n';
// cout<<now<<" "<<tr[now].l<<" "<<tr[now].r<<" "<<tr[now].num_b<<" "<<tr[now].num_w<<"=====================\n";
// for(int i=1;i<=n;i++) cout<<"=-="<<tr[now].bup[i].x<<" "<<tr[now].bup[i].y<<" "<<tr[now].bdn[i].x<<" "<<tr[now].bdn[i].y<<'\n';
}
void pushup(int now)
{
for(int i=1;i<=n;i++)
{
tr[now].bup[i]=tr[now<<1].bup[i];
tr[now].bdn[i]=tr[now<<1|1].bdn[i];
a[tr[now<<1].l][i]=tr[now<<1].bup[i];
a[tr[now<<1].r][i]=tr[now<<1].bdn[i];
a[tr[now<<1|1].l][i]=tr[now<<1|1].bup[i];
a[tr[now<<1|1].r][i]=tr[now<<1|1].bdn[i];
}
tr[now].num_b=tr[now<<1].num_b+tr[now<<1|1].num_b;
tr[now].num_w=tr[now<<1].num_w+tr[now<<1|1].num_w;
// cout<<"=-=-=-="<<tr[now].num_b<<" "<<tr[now].num_w<<'\n';
int up=tr[now<<1].r,dn=tr[now<<1|1].l;
for(int i=1;i<=n;i++)
{
if(t[up][i]==t[dn][i])
{
// cout<<"==="<<i<<'\n';
// cout<<"-"<<BOSS({up,i}).x<<" "<<BOSS({up,i}).y<<" "<<BOSS({dn,i}).x<<" "<<BOSS({dn,i}).y<<'\n';
if(BOSS({up,i})!=BOSS({dn,i}))
{
// cout<<"--"<<BOSS({up,i}).x<<" "<<BOSS({up,i}).y<<" "<<BOSS({dn,i}).x<<" "<<BOSS({dn,i}).y<<'\n';
if(t[up][i]) tr[now].num_b--;
else tr[now].num_w--;
HB({up,i},{dn,i});//,printf("!!! %d\n",i);
}
}
}
int num=0;
for(int i=1;i<=n;i++)
{
tr[now].bup[i]=BOSS(tr[now].bup[i]);
if(tr[now].bup[i].x!=tr[now].r&&tr[now].bup[i].x!=tr[now].l)
a[tr[now].bup[i].x][tr[now].bup[i].y]=tr[now].bup[i]={tr[now].l,i};
tr[now].bdn[i]=BOSS(tr[now].bdn[i]);
if(tr[now].bdn[i].x!=tr[now].r&&tr[now].bdn[i].x!=tr[now].l)
a[tr[now].bdn[i].x][tr[now].bdn[i].y]=tr[now].bdn[i]={tr[now].r,i};
// if(i==6&&up==5&&dn==6){
// printf("%d %d\n",tr[now].bup[i].x,tr[now].bup[i].y);
// if(vis[tr[now].bup[i].x][tr[now].bup[i].y].x)
// puts("vis");
// }
// printf("%d %d\n",tr[now].bup[i].x,tr[now].bup[i].y);
// printf("%d\n",i);
// for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){
// printf("%d %d |%c",vis[i][j].x,vis[i][j].y," \n"[j==n]);
// }
// if(vis[tr[now].bup[i].x][tr[now].bup[i].y].x)
// tr[now].bup[i]=vis[tr[now].bup[i].x][tr[now].bup[i].y];
// else
// {
// ls[++num]={tr[now].bup[i].x,tr[now].bup[i].y};
// vis[tr[now].bup[i].x][tr[now].bup[i].y]=tr[now].bup[i]={tr[now].l,i};
// }
// if(vis[tr[now].bdn[i].x][tr[now].bdn[i].y].x)
// tr[now].bdn[i]=vis[tr[now].bdn[i].x][tr[now].bdn[i].y];
// else
// {
// ls[++num]={tr[now].bdn[i].x,tr[now].bdn[i].y};
// vis[tr[now].bdn[i].x][tr[now].bdn[i].y]=tr[now].bdn[i]={tr[now].r,i};
// }
}
// for(int i=1;i<=num;i++) vis[ls[i].x][ls[i].y]={0,0},ls[i]={0,0};
// cout<<"pushup"<<now<<" "<<tr[now].l<<" "<<tr[now].r<<" "<<tr[now].num_b<<" "<<tr[now].num_w<<"=====================\n";
// for(int i=1;i<=n;i++) cout<<"=-="<<tr[now].bup[i].x<<" "<<tr[now].bup[i].y<<" "<<tr[now].bdn[i].x<<" "<<tr[now].bdn[i].y<<'\n';
}
void JS(int now,int l,int r)
{
tr[now].l=l;
tr[now].r=r;
if(l==r)
{
cll(now,l);
return;
}
int mid=(l+r)>>1;
JS(now<<1,l,mid);
JS(now<<1|1,mid+1,r);
pushup(now);
// cout<<now<<" "<<tr[now].l<<" "<<tr[now].r<<" "<<tr[now].num_b<<" "<<tr[now].num_w<<"=====================\n";
// for(int i=1;i<=n;i++) cout<<"=-="<<tr[now].bup[i].x<<" "<<tr[now].bup[i].y<<" "<<tr[now].bdn[i].x<<" "<<tr[now].bdn[i].y<<'\n';
}
void zhuan(int now,int x,int y)
{
if(tr[now].l==tr[now].r)
{
t[x][y]^=1;
// cout<<"=-=-=-=-=-=-=-=-=-=-=-=-=-"<<t[x][y]<<"=-=-=-="<<'\n';
cll(now,x);
return;
}
int mid=tr[now<<1].r;
if(mid>=x) zhuan(now<<1,x,y);
else zhuan(now<<1|1,x,y);
pushup(now);
}
int main()
{
// freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>t[i][j];
JS(1,1,n);
// cout<<tr[1].num_b<<" "<<tr[1].num_w<<'\n';
cin>>m;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
zhuan(1,x,y);
cout<<tr[1].num_b<<" "<<tr[1].num_w<<'\n';
}
return (0-0);
}
/*
4
1 0 1 0
0 0 0 1
0 0 1 0
0 1 0 1
1
3 4
1 0 1 0
0 0 0 1
0 0 1 1
0 1 0 1
*/