Solution - P7963 [NOIP2021] 棋局

Posted on Edited on

P7963 [NOIP2021] 棋局

写了一个下午捏。。。

先考虑骗分。

首先前六个点直接暴力就完事了，可以拿到 2424 分。

7,87,8 两个点只有普通道路，也很容易就能拿到。这样就有 3232 分了。

以上是不需要技巧就可以拿到的分。

但是对于二、三类边是完全没有头绪，因为每次要分解连通块，不好维护。

关键思路 11 ：离线所有询问，倒序处理，将添点变为删点；把分解连通块转化为合并连通块。

对于一类边，单独判断即可。

对于二类边，可以借助并查集，维护每条链的左右端点维护。

会了这两类边，就可以拿到 4444 分的好成绩了。

对于三类边，可以采用并查集 + 线段树合并维护：对于每个连通块（不包括有棋子的点），开一个以编号为权值的线段树用于维护该连通块的大小，再开两个以 lvlv 为权值的线段树维护所有该连通块能到达的棋子（黑、白分开维护）。

但是又有一个问题产生（最后才发现捏）：合并两个联通块时，维护棋子的线段树合并时会重复计算。

关键思路 22 ：由于同级别时，后下的能吃先下的，故可离散化 lvlv 数组，使每个点的 lvlv 唯一， mergemerge 的时候直接“ ∣| ”就可以去重了。

这样的话，我们就可以分别计算出 33 类边的贡献了。

但是这么做依然是有问题的：贡献可能重复。

对于一类边和二、三类边的重复，直接特判就行了。

对于二类边和三类边的重复比较复杂。二类边两个端点是可以特判的，但是中间部分不好算。

这个时候，我们可以发现，不存在二类边和不存在三类边的部分分已经拿到了。后面还有三个点 n,m≤1000n,m\leq 1000 ，可以暴力判断重复，也可以拿到。期望得分 6868 。

关键思路 33 ： 二类边连通块的编号是连续的一个区间，可以在三类边线段树内查询。

对于横竖两种二类边连通块，可以开两个三类边的编号线段树维护。这样就可以很好地计算重复的贡献了。

所以就在 O(T⋅n⋅m⋅log⁡(n⋅m+q))O(T\cdot n\cdot m\cdot\log (n\cdot m + q)) 的时间内解决了这个问题。

细节贼多。。

最后由于除法很慢还要小卡一个常捏（卡常前硬生生被卡成了 5656 分）。

比赛的时候要注意随时卡常。

很短的，也就 7k ，比猪国杀少 2k。

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
#include<bits/stdc++.h>
#define gc getchar
#define pc putchar
#define F(i,x,y) for(int i=x;i<=y;++i)
#define R(i,x,y) for(int i=x;i>=y;--i)
inline int min(int x,int y){ return x<y?x:y; }
inline int max(int x,int y){ return x>y?x:y; }
inline int read(){
	int x=0;char ch=gc();while (!isdigit(ch)) ch=gc();
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^'0'),ch=gc();return x;
}
inline int get_one_digit(){ char ch=gc();while (!isdigit(ch)) ch=gc();return ch^'0'; }
inline void print(int x){ if (x>9) print(x/10);pc('0'+x%10); }
using namespace std;
const int N=2e5+5,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int n,m,q,ddd[4];
int col[N],lv[N];
int minR[N],maxR[N],minC[N],maxC[N],faR[N],faC[N];//¶þºÅ±ßºáÏò¡¢×ÝÏòµÄ×îС¡¢×î´ó±êºÅ¡£ 
int fah[N],rtR[N],rtC[N],rtlv[N][2];
int findR(int x){ return faR[x]==x?x:(faR[x]=findR(faR[x])); }
int findC(int x){ return faC[x]==x?x:(faC[x]=findC(faC[x])); }
int findh(int x){ return fah[x]==x?x:(fah[x]=findh(fah[x])); }
int T[N*100],son[N*100][2],st[N*100],top,tot;
int G[N][4],ans[N];
int qx[N],qy[N],qcol[N],qlv[N];
int vis[N];
struct node{
	int val,tag;
} lisanhua[N];
inline bool operator < (node a,node b){ return a.val==b.val?a.tag<b.tag:a.val<b.val; }
inline int addnod(){ int cur=(top?st[top--]:++tot);son[cur][0]=son[cur][1]=T[cur]=0;return cur; }
inline int qson(int k,int p){ return son[k][p]?son[k][p]:(son[k][p]=addnod()); }
inline void del(int k){ T[k]=son[k][0]=son[k][1]=0;st[++top]=k; }
inline void pushup(int k){ T[k]=T[son[k][0]]+T[son[k][1]]; }
inline int merge(int p,int q,int l,int r){
	if (!p||!q) return p+q;
	if (l==r){
		T[p]|=T[q];
		return del(q),p;
	}
	int mid=l+r>>1;
	son[p][0]=merge(son[p][0],son[q][0],l,mid);
	son[p][1]=merge(son[p][1],son[q][1],mid+1,r);
	return pushup(p),del(q),p;
}
inline int Query(int k,int l,int r,int le,int ri){
	if (!k) return 0;
	if (l>=le&&r<=ri) return T[k];
	int mid=l+r>>1,res=0;
	if (mid>=le&&son[k][0]) res+=Query(son[k][0],l,mid,le,ri);
	if (mid< ri&&son[k][1]) res+=Query(son[k][1],mid+1,r,le,ri);
	return res;
}
inline void Add(int k,int l,int r,int p,int qwq){
	if (l==r) return T[k]+=qwq,void();
	int mid=l+r>>1;
	if (mid>=p) Add(qson(k,0),l,mid,p,qwq);
	else Add(qson(k,1),mid+1,r,p,qwq);
	pushup(k);
}/*
inline void Delete(int k){
	if (!k) return;
	Delete(son[k][0]),Delete(son[k][1]);
	del(k);
}*/
inline int num(int x,int y){ return (x-1)*m+y; }/*
inline int numf(int cur){
	int x=(cur-1)/m+1,y=(cur-1)%m+1;
	return (y-1)*n+x;
}
inline int rnumf(int cur){
	int x=(cur-1)/n+1,y=(cur-1)%n+1;
	return (y-1)*m+x;
}*/
int numf[N],rnumf[N];
#define numf(x) numf[x]
#define rnumf(x) rnumf[x]
inline int pos(int cur,int f){ return cur+ddd[f]; }
void Dfs(int cur,int p){
	F(i,0,3){
		if (G[cur][i]!=3) continue;
		int to=pos(cur,i);
		if (vis[to]) continue;
		if (lv[to]){
			vis[to]=1;
			if (!rtlv[p][col[to]]) rtlv[p][col[to]]=addnod();
			Add(rtlv[p][col[to]],1,q,lv[to],1);
		}else{
			vis[to]=1,Dfs(to,p);
			rtR[p]=merge(rtR[p],rtR[to],1,n*m);
			rtC[p]=merge(rtC[p],rtC[to],1,n*m);
			fah[to]=p;
		}
	}
}
void Dfs2(int cur){
	F(i,0,3){
		if (G[cur][i]!=3) continue;
		int to=pos(cur,i);
		if (vis[to]!=1) continue;
		if (lv[to]){
			vis[to]=0;
		}else{
			vis[to]=2,Dfs2(to);
		}
	}
}
inline void INIT(){
	top=tot=0;
	n=read(),m=read(),q=read();
	F(i,1,n) F(j,1,m){
		numf[(i-1)*m+j]=(j-1)*n+i;
		rnumf[(j-1)*n+i]=(i-1)*m+j;
	}
	F(i,1,q) ans[i]=0;
	ddd[0]=m,ddd[1]=1,ddd[2]=-m,ddd[3]=-1;
	F(i,1,n*m){
		col[i]=lv[i]=0;
		vis[i]=0;
		minR[i]=maxR[i]=i;
		minC[i]=maxC[i]=numf(i);
		faR[i]=faC[i]=fah[i]=i;
		rtR[i]=rtC[i]=rtlv[i][0]=rtlv[i][1]=0;
	}
	F(i,1,n) F(j,1,m-1){
		int op=get_one_digit(),cur=num(i,j),to=num(i,j+1);
		G[cur][1]=op,G[to][3]=op;
	}
	F(i,1,n-1) F(j,1,m){
		int op=get_one_digit(),cur=num(i,j),to=num(i+1,j);
		G[cur][0]=op,G[to][2]=op;
	}
	F(i,1,q){
		qcol[i]=read(),qlv[i]=read(),qx[i]=read(),qy[i]=read();
		int cur=num(qx[i],qy[i]);
		col[cur]=qcol[i];
		lisanhua[i].val=qlv[i],lisanhua[i].tag=i;
	}
	std::sort(lisanhua+1,lisanhua+1+q);
	F(i,1,q){
		qlv[lisanhua[i].tag]=i;
	}
	F(i,1,q){
		lv[num(qx[i],qy[i])]=qlv[i];
	}
	F(i,1,n*m){
		if (!lv[i]){
			rtR[i]=addnod(),Add(rtR[i],1,n*m,i,1);
			rtC[i]=addnod(),Add(rtC[i],1,n*m,numf(i),1);
		}
	}
	//´¦ÀíÈýºÅ±ß
	F(i,1,n*m){
		if (!vis[i]&&!lv[i]) vis[i]=1,Dfs(i,i),vis[i]=2,Dfs2(i);
	}
	//´¦Àí¶þºÅ±ßR
	F(i,1,n){
		int p=0;
		F(j,1,m){
			int cur=num(i,j);
			if (lv[cur]) p=0;
			else if (p==0) p=cur;
			else{
				if (G[cur][3]==2) faR[findR(cur)]=p,maxR[p]=cur;
				else p=cur;
			}
		}
	}//0down 1right 2up 3left
	//C
	F(j,1,m){
		int p=0;
		F(i,1,n){
			int cur=num(i,j);
			if (lv[cur]) p=0;
			else if (p==0) p=cur;
			else{
				if (G[cur][2]==2) faC[findC(cur)]=p,maxC[p]=numf(cur);
				else p=cur;
			}
		}
	}
}
inline bool pd(int cur,int p){
	if (cur>n*m||cur<1) return 0;
	if (!lv[cur]) return findh(cur)!=p;
	F(i,0,3){
		if (G[cur][i]!=3) continue;
		int to=pos(cur,i);
		if (findh(to)==p&&to!=p) return 0;
	}
	return 1;
}
bool got[N];
inline void WORK(){
	R(t,q,1){
		//3
		int cur=num(qx[t],qy[t]);
		F(j,0,3){
			if (G[cur][j]!=3) continue;
			int to=pos(cur,j);
			int ft=findh(to);
			if (!lv[to]&&!got[ft]){
				got[ft]=1;
				Add(rtlv[ft][col[cur]],1,q,lv[cur],-1);
			}
		}
		F(j,0,3){
			if (G[cur][j]!=3) continue;
			int to=pos(cur,j);
			int ft=findh(to);
			if (got[ft]){
				got[ft]=0;
			}
		}
		rtR[cur]=addnod(),Add(rtR[cur],1,n*m,cur,1);
		rtC[cur]=addnod(),Add(rtC[cur],1,n*m,numf(cur),1);
		F(j,0,3){
			if (G[cur][j]!=3) continue;
			int to=pos(cur,j);
			int ft=findh(to);
			if (!lv[to]&&ft!=cur){
				rtlv[cur][0]=merge(rtlv[cur][0],rtlv[ft][0],1,q);
				rtlv[cur][1]=merge(rtlv[cur][1],rtlv[ft][1],1,q);
				rtR[cur]=merge(rtR[cur],rtR[ft],1,n*m);
				rtC[cur]=merge(rtC[cur],rtC[ft],1,n*m);
				fah[ft]=cur;
			}
		}
		F(j,0,3){
			if (G[cur][j]!=3) continue;
			int to=pos(cur,j);
			if (lv[to]&&pd(to,cur)){
				if (!rtlv[cur][col[to]]) rtlv[cur][col[to]]=addnod();
				Add(rtlv[cur][col[to]],1,q,lv[to],1);
			}
		}
		//2
		minR[cur]=maxR[cur]=cur;
		minC[cur]=maxC[cur]=numf(cur);
		F(j,0,3){
			if (G[cur][j]!=2) continue;
			int to=pos(cur,j);
			if (lv[to]) continue;
			if (j%2){
				int fr=findR(to);
				minR[cur]=min(minR[cur],minR[fr]);
				maxR[cur]=max(maxR[cur],maxR[fr]);
				faR[fr]=cur;
			}else{
				int fc=findC(to);
				minC[cur]=min(minC[cur],minC[fc]);
				maxC[cur]=max(maxC[cur],maxC[fc]);
				faC[fc]=cur;
			}
		}
		//ans
		ans[t]+=T[rtR[cur]]-1+Query(rtlv[cur][col[cur]^1],1,q,1,lv[cur]);
		ans[t]+=maxR[cur]-minR[cur]+maxC[cur]-minC[cur];
		int to=maxR[cur]+1;
		ans[t]+=(G[maxR[cur]][1]==2&&pd(to,cur)&&col[to]!=col[cur]&&lv[to]<=lv[cur]);
		to=minR[cur]-1;
		ans[t]+=(G[minR[cur]][3]==2&&pd(to,cur)&&col[to]!=col[cur]&&lv[to]<=lv[cur]);
		to=rnumf(maxC[cur])+m;
		ans[t]+=(G[rnumf(maxC[cur])][0]==2&&pd(to,cur)&&col[to]!=col[cur]&&lv[to]<=lv[cur]);
		to=rnumf(minC[cur])-m;
		ans[t]+=(G[rnumf(minC[cur])][2]==2&&pd(to,cur)&&col[to]!=col[cur]&&lv[to]<=lv[cur]);
		F(j,0,3){
			int to=pos(cur,j);
			ans[t]+=(G[cur][j]==1&&pd(to,cur)&&(lv[to]&&col[to]!=col[cur]&&lv[to]<=lv[cur]||!lv[to]));
		}
		ans[t]-=Query(rtR[cur],1,n*m,minR[cur],maxR[cur])-1;
		ans[t]-=Query(rtC[cur],1,n*m,minC[cur],maxC[cur])-1;
		lv[cur]=col[cur]=0;
	}
}//0down 1right 2up 3left
signed main(){
	//freopen("chess3.in","r",stdin),freopen("1A.out","w",stdout);
	//return system("fc chess3.ans 1A.out"),0;
	int T=read();
	F(test,1,T){
		INIT();
		WORK();
		F(i,1,q) print(ans[i]),pc('\n');
		F(i,1,n*m){
			//if (fah[i]==i) Delete(rtlv[i][0]),Delete(rtlv[i][1]),Delete(rtC[i]),Delete(rtR[i]);
			F(j,0,3) G[i][j]=0;
		}
	}
	return 0;
}