WC2005 双面棋盘 题解

Posted on

赛后写题解补教训

场上数组开小本机AC但开了O2就会RE=爆零

洛谷上测由于数组开小导致访问不到死递归MLE我还以为还是开大了

小心，小心，再小心

我们尝试建立一棵线段树。

线段树的每一个叶子节点是一行，每一个节点是一段行。

每一个节点存上两个东西：

  • 两个并查集，记录这个节点所对应的行区间的最上面一行和最下面一行的状态（后面会讲到）

  • 这个区间内部两种颜色的连通块的个数

对于单独的每一行，我们搞一个并查集：如果在这一行中，$i\dots j$ 的颜色相同，那么我们把 $i\dots j$ 都放到同一个集合中。用最小表示法，这个集合的代表就是最小的元素 $i$。

我们考虑合并两个行区间。

显然，新的行区间的上并查集就是左儿子的上并查集，新区间的下并查集就是右儿子的下并查集。

考虑左儿子的下并查集与右儿子的上并查集结合所带来的贡献。

首先令新节点的颜色 $c$ 的连通块数等于其两个儿子的该颜色的连通块数之和。

然后枚举，对于第 $i$ 列，如果 $gird_{md,i} = gird_{md+1,i}$，那么显然这两个在同一个连通块中，要将该颜色的数量-1。

然后写个标准的线段树就完事了~

总时间复杂度 O(能过) $O(n^2+mnlogn)$

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define int short
using namespace std;
const int mxn=808;
int gird[mxn][mxn],n,m,q;
	struct dsu{
		int fa[mxn<<1];
		inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
		inline void uni(int x,int y){
			x=find(x),y=find(y);
			fa[x]=y;
		}
		inline void init(){for(int i=1;i<(mxn<<1);++i)fa[i]=i;}
	}f;
	int stand[mxn];
	struct node{
		dsu d;
		int son[2],ans[2];
		inline void init(){
			ans[0]=0,ans[1]=0;d.init();
			son[0]=0,son[1]=0;
		}
	}t[mxn<<1];
	inline void ForceUpdate(int id,int x){
		t[id].init();
		t[id].ans[gird[x][1]]=1;
		t[id].ans[1-gird[x][1]]=0;
		int pre=1;
		for(int i=1;i<=m;++i){
			if(gird[x][i]!=gird[x][pre]){
				++t[id].ans[gird[x][i]];
				pre=i;
			}
			t[id].d.uni(i,pre),t[id].d.uni(i+n,pre);
		}
	}
	inline void pushup(int id,int md,int l,int r){
		f.init();
		for(int i=0;i<2;++i)t[id].ans[i]=t[l].ans[i]+t[r].ans[i];
		for(int i=1;i<=m*2;++i)f.fa[i]=t[l].d.fa[i],f.fa[i+m*2]=t[r].d.fa[i]+m*2;
		for(int i=1;i<=m;++i){
			int fx=f.find(i+m),fy=f.find(i+2*m);
			if(gird[md][i]==gird[md+1][i] and fx!=fy){
				--t[id].ans[gird[md][i]];
				f.uni(fx,fy);
			}
		}
		memset(stand,0,sizeof(stand));     // stand 数组的用处是最小表示
		for(int i=m;i;--i){
			f.fa[i]=f.find(i);
			stand[f.fa[i]]=i;
		}
		for(int i=m*2;i>m;--i){
			f.fa[i+m*2]=f.find(i+m*2);
			stand[f.fa[i+m*2]]=i;
		}
		for(int i=1;i<=m;++i){
			t[id].d.fa[i]=stand[f.fa[i]];
			t[id].d.fa[i+m]=stand[f.fa[i+m*3]];
		}
	}
	int cntnode=0,root;
	inline void build(int&id,int l,int r){
		id=++cntnode;
		if(l==r){
			ForceUpdate(id,l);
			return;
		}
		int md=l+r>>1;
		build(t[id].son[0],l,md);
		build(t[id].son[1],md+1,r);
		pushup(id,md,t[id].son[0],t[id].son[1]);
	}
	inline void upd(int id,int l,int r,int x){
		if(l==r){
			ForceUpdate(id,x);
			return;
		}
		int md=l+r>>1;
		if(x<=md)upd(t[id].son[0],l,md,x);
		else upd(t[id].son[1],md+1,r,x);
		pushup(id,md,t[id].son[0],t[id].son[1]);
	}
	inline void glhf(){
		build(root,1,n);
		for(;q--;){
			int x,y;
			cin>>x>>y;
			gird[x][y]^=1;
			upd(root,1,n,x);
			cout<<t[root].ans[1]<<' '<<t[root].ans[0]<<'\n';
		}
	}
inline void solve(){
	cin>>n;m=n;
	for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)cin>>gird[i][j];
	cin>>q;
	glhf();
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T;T=1;
//	cin>>T;
	for(;T--;)solve();
	return 0;
}