md,我人要调没了(((
查看原帖
md,我人要调没了(((
260886
YT0104楼主2023/7/30 17:28

就是有这样一份代码,它用来输出调试的语句已经比代码长了(((

我人要麻了,就写的是 线段树+并查集,但是就是错了

dalao们帮忙调一下吧,球球了!蒟蒻已经调了4天了QAQQAQ

有不知所云的地方随时问我,我全天 16+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 
*/
2023/7/30 17:28
加载中...