自动搬运

查看原文

来自洛谷，原作者为

	破壁人五号 「不过回归空白　空白的原来」| AFO | ICPCer | wallbreaker5th.top

搬运于2025-08-24 22:34:43，当前版本为作者最后更新于2021-11-30 10:38:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

棋子会将棋盘分开为若个部分，分裂过程不好维护。故先离线所有询问，将添加棋子改为删除棋子。

为了方便，我们略微更改棋子的等级，使其两两不同。

我们首先考虑 3 类边。我们维护三类边组成的连通块，每个连通块需要维护四个数据结构：

• 其连到的白子的等级（我们需要查询等级小于等于给定值的棋子个数）；
• 其连到的黑子的等级（我们需要查询等级小于等于给定值的棋子个数）；
• 空位，同一行的空位应当连续（我们需要查询一行的某一段中包含多少空位）；
• 空位，同一列的空位应当连续（我们需要查询一列的某一段中包含多少空位）；

同时我们还需要支持合并两个连通块、删除一个棋子。其可以用并查集+线段树合并实现。

接着考虑 2 类边。我们直接维护两个（横向与纵向的）并查集，分别维护 2 类边构成的连通块。为了不与 3 类边算重，我们要去掉：

• 2 类连通块两端的棋子，如果出现在 3 类连通块中；
• 2 类连通块内的空白段，将这个段放到 3 类连通块内查询。

最后考虑 1 类边，我们依次检查其相邻的几个位置，如果它们没有在 2 或 3 类边中统计过，则加进答案中。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5;
#define x first
#define y second
#define pii pair<int,int>
int n,m,q,idlim;
int idh(int x,int y){ return x*(m+2)+y; }
pii hdi(int id){ return pii(id/(m+2),id%(m+2)); }
int idv(int x,int y){ return y*(n+2)+x; }
pii vdi(int id){ return pii(id%(n+2),id/(n+2)); }
template<class T>
struct array2d{
	T a[N];
	int n,m;
	void init(int val=0){
		memset(a,val,sizeof(a));
	}
	void set_size(int n,int m,int val=0){
		this->n=n;
		this->m=m;
		init(val);
	}
	T* operator[](int i){
		return a+i*(m+2);
	}
	const T* operator[](int i)const{
		return a+i*(m+2);
	}
	T& operator[](pii p){
		return a[p.x*(m+2)+p.y];
	}
	const T& operator[](pii p)const{
		return a[p.x*(m+2)+p.y];
	}
};
array2d<int> v,h,col,lv,tim;
vector<pii> piece;

struct node{
	int ch[2],sz;
};
node t[N*30];int cnt;
void pushup(int x){
	t[x].sz=t[t[x].ch[0]].sz+t[t[x].ch[1]].sz;
}
void insert(int p,int &x,int l,int r){
	if(!x)x=++cnt;
	if(l==r){ t[x].sz=1;return; }
	int mid=(l+r)>>1;
	if(p<=mid)insert(p,t[x].ch[0],l,mid);
	else insert(p,t[x].ch[1],mid+1,r);
	pushup(x);
}
void erase(int p,int &x,int l,int r){
	if(!x)return;
	if(l==r){ t[x].sz=0;return; }
	int mid=(l+r)>>1;
	if(p<=mid)erase(p,t[x].ch[0],l,mid);
	else erase(p,t[x].ch[1],mid+1,r);
	pushup(x);
}
int merge(int x,int y){
	if(!(x&&y))return x+y;
	t[x].ch[0]=merge(t[x].ch[0],t[y].ch[0]);
	t[x].ch[1]=merge(t[x].ch[1],t[y].ch[1]);
	if(t[x].ch[0]||t[x].ch[1])pushup(x);
	else t[x].sz|=t[y].sz;
	return x;
}
int query_rk(int v,int x,int l,int r){
	if(!t[x].sz)return 0;
	if(l==r)return t[x].sz;
	int mid=(l+r)>>1;
	if(v<=mid)return query_rk(v,t[x].ch[0],l,mid);
	else return t[t[x].ch[0]].sz+query_rk(v,t[x].ch[1],mid+1,r);
}
bool exist(int v,int x,int l,int r){
	if(!t[x].sz)return 0;
	if(l==r)return 1;
	int mid=(l+r)>>1;
	if(v<=mid)return exist(v,t[x].ch[0],l,mid);
	else return exist(v,t[x].ch[1],mid+1,r);
}

struct DSU_with_lr{
	int l[N],r[N],f[N];
	int _(int x){ return f[x]==x?x:f[x]=_(f[x]); }
	void merge(int x,int y){
		x=_(x),y=_(y);
		if(x==y)return;
		f[x]=y;
		l[y]=min(l[y],l[x]);
		r[y]=max(r[y],r[x]);
	}
	int getl(int id){ return l[_(id)]; }
	int getr(int id){ return r[_(id)]; }
	bool check(int x,int y){ return _(x)==_(y); }
};
DSU_with_lr hseg,vseg;

struct block{
	int rt0,rt1,rth,rtv;
	void merge(block &y){
		rt0=::merge(rt0,y.rt0);
		rt1=::merge(rt1,y.rt1);
		rth=::merge(rth,y.rth);
		rtv=::merge(rtv,y.rtv);
	}
	int get0(int v){ return query_rk(v,rt0,1,q); }
	void ins0(int v){ insert(v,rt0,1,q); }
	void era0(int v){ erase(v,rt0,1,q); }
	int get1(int v){ return query_rk(v,rt1,1,q); }
	void ins1(int v){ insert(v,rt1,1,q); }
	void era1(int v){ erase(v,rt1,1,q); }
	void ins01(int col,int v){ col?ins1(v):ins0(v); }
	void era01(int col,int v){ col?era1(v):era0(v); }
	void insp(int x,int y){
		insert(idh(x,y),rth,1,idlim);
		insert(idv(x,y),rtv,1,idlim);
	}
	int getsz(int col,int lv){
		return t[rth].sz+(1-col?get1(lv):get0(lv));
	}
	int geth(int x,int y1,int y2,int colx,int lvx){
		auto check=[&](int p,int q){
			return col[p][q]==1-colx&&lv[p][q]<=lvx&&exist(lv[p][q],1-colx?rt1:rt0,1,::q);
		};
		return query_rk(idh(x,y2),rth,1,idlim)-query_rk(idh(x,y1-1),rth,1,idlim)
			  +(h[x][y1-1]==2&&check(x,y1-1))+(h[x][y2]==2&&check(x,y2+1));
	}
	int getv(int x1,int x2,int y,int colx,int lvx){
		auto check=[&](int p,int q){
			return col[p][q]==1-colx&&lv[p][q]<=lvx&&exist(lv[p][q],1-colx?rt1:rt0,1,::q);
		};
		return query_rk(idv(x2,y),rtv,1,idlim)-query_rk(idv(x1-1,y),rtv,1,idlim)
			  +(v[x1-1][y]==2&&check(x1-1,y))+(v[x2][y]==2&&check(x2+1,y));
	}
};
template<class T>
struct DSU_array2d{
	array2d<T>a;
	array2d<pii>f;
	void init(int val=0){
		a.init(val);
	}
	void set_size(int n,int m,int val=0){
		a.set_size(n,m,val);
		f.set_size(n,m,val);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				f[i][j]={i,j};
	}
	pii _(pii x){ return x==f[x]?x:f[x]=_(f[x]); }
	T& operator[](pii p){
		return a[_(p)];
	}
	void merge(pii x,pii y){
		x=_(x),y=_(y);
		if(x==y)return;
		a[x].merge(a[y]);
		f[y]=x;
	}
};
DSU_array2d<block> b;

int qsum=0;
int ans[N];
int lvcnt[N];
void mian(){
	cin>>n>>m>>q;
	v.set_size(n,m);
	h.set_size(n,m);
	col.set_size(n,m,-1);
	lv.set_size(n,m);
	tim.set_size(n,m);
	piece.clear();
	memset(t,0,sizeof(t));
	memset(&hseg,0,sizeof(hseg));
	memset(&vseg,0,sizeof(vseg));
	memset(lvcnt,0,sizeof(lvcnt));
	b.set_size(n,m);
	for(int i=0;i<N;i++)hseg.l[i]=hseg.r[i]=hseg.f[i]=i;
	for(int i=0;i<N;i++)vseg.l[i]=vseg.r[i]=vseg.f[i]=i;
	idlim=(n+3)*(m+3);

	cnt=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<m;j++){
			char c;cin>>c;
			h[i][j]=c-'0';
		}
	for(int i=1;i<n;i++)
		for(int j=1;j<=m;j++){
			char c;cin>>c;
			v[i][j]=c-'0';
		}
	for(int i=1;i<=q;i++){
		int colx,lvx,x,y;
		cin>>colx>>lvx>>x>>y;
		col[x][y]=colx;
		lv[x][y]=lvx;
		++lvcnt[lvx];
		tim[x][y]=i;
		piece.push_back(pii(x,y));
	}
	for(int i=1;i<=q;i++)lvcnt[i]+=lvcnt[i-1];
	for(int i=q-1;i>=0;--i)lv[piece[i].x][piece[i].y]=lvcnt[lv[piece[i].x][piece[i].y]]--;
	for(int i=1;i<=n;i++){
		for(int j=1;j<m;j++){
			if(h[i][j]==2&&!lv[i][j]&&!lv[i][j+1])hseg.merge(idh(i,j),idh(i,j+1));
			if(h[i][j]==3&&!lv[i][j]&&!lv[i][j+1])b.merge({i,j},{i,j+1});
			if(h[i][j]==3&&lv[i][j]&&!lv[i][j+1]){
				b[{i,j+1}].ins01(col[i][j],lv[i][j]);
			}
			if(h[i][j]==3&&!lv[i][j]&&lv[i][j+1]){
				b[{i,j}].ins01(col[i][j+1],lv[i][j+1]);
			}
		}
	}
	for(int i=1;i<n;i++){
		for(int j=1;j<=m;j++){
			if(v[i][j]==2&&!lv[i][j]&&!lv[i+1][j])vseg.merge(idv(i,j),idv(i+1,j));
			if(v[i][j]==3&&!lv[i][j]&&!lv[i+1][j])b.merge({i,j},{i+1,j});
			if(v[i][j]==3&&lv[i][j]&&!lv[i+1][j]){
				b[{i+1,j}].ins01(col[i][j],lv[i][j]);
			}
			if(v[i][j]==3&&!lv[i][j]&&lv[i+1][j]){
				b[{i,j}].ins01(col[i+1][j],lv[i+1][j]);
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(!lv[i][j]){
				b[{i,j}].insp(i,j);
			}
		}
	}
	for(int i=q-1;i>=0;--i){
		int ans=-1;
		int x=piece[i].x,y=piece[i].y;
		int lvx=lv[x][y],colx=col[x][y];
		lv[x][y]=0; col[x][y]=-1;

		if(h[x][y]==2&&!lv[x][y]&&!lv[x][y+1])hseg.merge(idh(x,y),idh(x,y+1));
		if(h[x][y-1]==2&&!lv[x][y-1]&&!lv[x][y])hseg.merge(idh(x,y-1),idh(x,y));
		pii l=hdi(hseg.getl(idh(x,y))),r=hdi(hseg.getr(idh(x,y)));
		ans+=r.y-l.y+1;

		if(v[x][y]==2&&!lv[x][y]&&!lv[x+1][y])vseg.merge(idv(x,y),idv(x+1,y));
		if(v[x-1][y]==2&&!lv[x-1][y]&&!lv[x][y])vseg.merge(idv(x-1,y),idv(x,y));
		pii u=vdi(vseg.getl(idv(x,y))),d=vdi(vseg.getr(idv(x,y)));
		ans+=d.x-u.x+1;

		b[{x,y}].insp(x,y);
		if(h[x][y]==3){
			if(!lv[x][y+1])b.merge({x,y},{x,y+1});
			else b[{x,y}].ins01(col[x][y+1],lv[x][y+1]);
		}
		if(h[x][y-1]==3){
			if(!lv[x][y-1])b.merge({x,y-1},{x,y});
			else b[{x,y}].ins01(col[x][y-1],lv[x][y-1]);
		}
		if(v[x][y]==3){
			if(!lv[x+1][y])b.merge({x,y},{x+1,y});
			else b[{x,y}].ins01(col[x+1][y],lv[x+1][y]);
		}
		if(v[x-1][y]==3){
			if(!lv[x-1][y])b.merge({x-1,y},{x,y});
			else b[{x,y}].ins01(col[x-1][y],lv[x-1][y]);
		}
		b[{x,y}].era01(colx,lvx);
		ans+=b[{x,y}].getsz(colx,lvx);
		ans-=b[{x,y}].geth(l.x,l.y,r.y,colx,lvx);
		ans-=b[{x,y}].getv(u.x,d.x,u.y,colx,lvx);

		if(col[l.x][l.y-1]==1-colx&&h[l.x][l.y-1]==2&&lv[l.x][l.y-1]<=lvx)++ans,--l.y;
		if(col[r.x][r.y+1]==1-colx&&h[r.x][r.y  ]==2&&lv[r.x][r.y+1]<=lvx)++ans,++r.y;
		if(col[u.x-1][u.y]==1-colx&&v[u.x-1][u.y]==2&&lv[u.x-1][u.y]<=lvx)++ans,--u.x;
		if(col[d.x+1][d.y]==1-colx&&v[d.x  ][d.y]==2&&lv[d.x+1][d.y]<=lvx)++ans,++d.x;
		
		auto check=[&](int p,int q){
			return !lv[p][q]||(col[p][q]==1-colx&&lv[p][q]<=lvx);
		};
		auto vis=[&](int p,int q){
			if(b._({p,q})==b._({x,y}))return 1;
			if(lv[p][q]&&exist(lv[p][q],col[p][q]?b[{x,y}].rt1:b[{x,y}].rt0,1,::q))return 1;
			return 0;
		};
		if(h[x][y]==1&&check(x,y+1)&&!vis(x,y+1))++ans;
		if(v[x][y]==1&&check(x+1,y)&&!vis(x+1,y))++ans;
		if(h[x][y-1]==1&&check(x,y-1)&&!vis(x,y-1))++ans;
		if(v[x-1][y]==1&&check(x-1,y)&&!vis(x-1,y))++ans;
		::ans[i]=ans;
	}
	for(int i=0;i<q;i++)cout<<ans[i]<<"\n";
	qsum+=q;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;cin>>T;
	while(T--){
		mian();
	}
}