线段树合并+并查集求调

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	auto _u=[](char x){return x>='0'&&x<='9';};
	for(;!_u(ch);ch=='-'&&(f=-1),ch=getchar());
	for(;_u(ch);x=(x<<1)+(x<<3)+(ch^48),ch=getchar());
	return x*f;
}
inline void write(int num,bool flag=0){
	static int st[39],tp=0;
	num<0&&(putchar('-'),num=-num);
	do st[++tp]=num%10;while(num/=10);
	while(tp) putchar(st[tp--]|48);
	putchar(flag?'\n':' ');
	return;
}
template<typename...Args>
inline void write(int t,Args...args){
	return write(t),write(args...);
}
const int N=2e5+10;
int n,m,q;
struct fffffyn{
	int b[N*39*5],ls[N*39*5],rs[N*39*5];
	int tot;
	inline void init(){
		tot=0;
	}
	#define MID(l,r) (((r-l)>>1)+l)
	inline int newnode(){
		++tot;
		b[tot]=ls[tot]=rs[tot]=0;
		return tot;
	}
	inline void pushup(int now){
		b[now]=b[ls[now]]+b[rs[now]];
	}
	inline void insert(int pos,int l,int r,int&now,int v=1){
		if(!now) now=newnode();
		if(l==r) return void(b[now]=v);
		int mid(MID(l,r));
		if(pos<=mid)insert(pos,l,mid,ls[now]);
		else insert(pos,mid+1,r,rs[now]);
		return pushup(now);
	}
	inline int merge(int p,int q,int l,int r){
		if(!p||!q)return p|q;
		if(l==r) return b[p]|=b[q],p;
		int mid(MID(l,r)),now=newnode();
		ls[now]=merge(ls[p],ls[q],l,mid);
		rs[now]=merge(rs[p],rs[q],mid+1,r);
		pushup(now);
		return now;
	}
	inline int query(int l,int r,int nl,int nr,int now){
		if(!now||l>r)return 0;
		if(l<=nl && nr<=r)return b[now];
		int mid(MID(nl,nr));
		if(l<=mid&&mid<=r)return query(l,r,nl,mid,ls[now])+query(l,r,mid+1,nr,rs[now]);
		if(l<=mid)return query(l,r,nl,mid,ls[now]);
		return query(l,r,mid+1,nr,rs[now]);
	}
}tre;
int rt[4][N];
inline void merg(int u,int v){
	rt[0][v]=tre.merge(rt[0][u],rt[0][v],1,q);
	rt[1][v]=tre.merge(rt[1][u],rt[1][v],1,q);
	rt[2][v]=tre.merge(rt[2][u],rt[2][v],1,n*m);
	rt[3][v]=tre.merge(rt[3][u],rt[3][v],1,n*m);
}

struct bcj{
	int sz[N],mx[N],mn[N],fa[N];
	inline void init(int x){
		for(int i=1;i<=x;++i)
			fa[i]=mx[i]=mn[i]=i,sz[i]=1;
	}
	inline int fnd(int u){
		return u==fa[u]?u:fa[u]=fnd(fa[u]);
	}
	inline void merge(int u,int v,bool flag=0){
		if((u=fnd(u))==(v=fnd(v)))return;
		if(sz[u]>sz[v])swap(u,v);
		fa[u]=v,sz[v]+=sz[u],mx[v]=max(mx[v],mx[u]),mn[v]=min(mn[u],mn[v]);
		if(flag)merg(u,v);
	}
}fat[4];

pair<int,int>uid[N]; 

inline int id(int x,int y){
	uid[(x-1)*m+y]=make_pair(x,y);
	return (x-1)*m+y;
}
inline int id2(int x,int y){
	return (y-1)*n+x;
}
struct node{
	int col,lv,x,y,id;
}a[N];
int b[N];
int e[4][N],d[4][2]={{-1,0},{0,-1},{1,0},{0,1}},rnk[N];
inline bool check(int x,int y){
	if(y<=0||y>x)return false;
	return a[x].col!=a[y].col&&a[x].lv>a[y].lv;
}

inline void init(){
	memset(e,0,sizeof e);
	for(int i=0;i<4;++i) fat[i].init(n*m);
	tre.init();
	memset(rt,0,sizeof rt);
}
char sop[N];
int ans[N];
signed main(){
	
	for(int T=read();T--;){
		n=read(),m=read(),q=read();
		init();
		for(int i=1;i<=n;++i){
			scanf("%s",sop+1);
			for(int j=1;j<m;++j)
				e[1][id(i,j+1)]=e[3][id(i,j)]=(sop[j]^48); 
		}
		for(int i=1;i<n;++i){
			scanf("%s",sop+1);
			for(int j=1;j<=m;++j)
				e[0][id(i+1,j)]=e[2][id(i,j)]=(sop[j]^48);
		}
		for(int i=1;i<=q;++i)a[i].col=read(),a[i].lv=read(),a[i].x=read(),a[i].y=read(),a[i].id=i;
		sort(a+1,a+q+1,[](node x,node y){return make_tuple(x.lv,x.id,x.x,x.y,x.col)<make_tuple(y.lv,y.id,y.x,y.y,y.col);});
		for(int i=1;i<=q;++i) a[i].lv=i;
		sort(a+1,a+q+1,[](node x,node y){return x.id<y.id;});
		for(int i=1;i<=q;++i) rnk[id(a[i].x,a[i].y)]=i;
		for(int i=1;i<=n;++i){
			for(int j=1,now,nxt;j<=m;++j){
				now=id(i,j);
				for(int k=0;k<4;++k)
					if(e[k][now]>1 && !rnk[now] && !rnk[nxt=id(i+d[k][0],j+d[k][1])])
						fat[e[k][now]==3?0:k%2+1].merge(now,nxt);
			}
		}
		for(int i=1;i<=n;++i)
			for(int j=1,now,fyn;j<=m;++j){
				fyn=fat[0].fnd(now=id(i,j));
				tre.insert(id2(i,j),1,n*m,rt[2][fyn]);
				tre.insert(now,1,n*m,rt[3][fyn]);
				for(int k=0,nxt;k<4;++k)
					if(e[k][now]==3)
						if(rnk[nxt=id(i+d[k][0],j+d[k][1])])
							tre.insert(a[rnk[nxt]].lv,1,q,rt[a[rnk[nxt]].col][fyn]);
			}
		
		for(int i=q,now,tmp,px,py;i;--i){
			now=id(px=a[i].x,py=a[i].y),tmp=a[i].col;
			
			for(int j=0,nxt;j<4;++j)
				if(e[j][now]==3){
					nxt=fat[0].fnd(id(px+d[j][0],py+d[j][1]));
					tre.insert(a[i].lv,1,q,rt[tmp][nxt],0);
					if(rnk[nxt]&&rnk[nxt]<i) continue;
					fat[0].merge(now,nxt,1); 
//					cout<<i<<":::"<<tmp<<' '<<nxt<<tre.query(6,6,1,q,rt[2][5])<<endl;
				}
			int iid;
			ans[i]=fat[0].sz[iid=fat[0].fnd(now)]+tre.query(1,a[i].lv,1,q,rt[!tmp][fat[0].fnd(now)]);
     		
//			 	write(ans[i]);
			 for(int j=0,nxt;j<4;++j)
				if(e[j][now]==2){
					if(!rnk[nxt=id(px+d[j][0],py+d[j][1])]||rnk[nxt]>=i)
						fat[j%2+1].merge(now,nxt);
				}
			int mx[3],mn[3];
			for(int j=1;j<=2;++j)
				mx[j]=fat[j].mx[fat[j].fnd(now)],
				mn[j]=fat[j].mn[fat[j].fnd(now)];
			ans[i]+=mx[2]-mn[2]+1+(mx[1]-mn[1])/m+1;
						
//						write(ans[i]);
			mx[0]=id2(uid[mx[1]].first,uid[mx[1]].second),mn[0]=id2(uid[mn[1]].first,uid[mn[1]].second);
			ans[i]-=tre.query(mn[0],mx[0],1,n*m,rt[2][iid])+tre.query(mn[2],mx[2],1,n*m,rt[3][iid]);
//						write(ans[i],tre.query(mn[0],mx[0],1,n*m,rt[2][iid]),tre.query(mn[2],mx[2],1,n*m,rt[3][iid]),mn[0],mx[0],true);
			auto solve=[tmp,iid,i](bool ff,int tt,int tt1){
				if(e[ff][tt]!=2||!check(i,rnk[tt1])) return false;
				return (bool)(!tre.query(a[rnk[tt1]].lv,a[rnk[tt1]].lv,1,q,rt[!tmp][iid]));
			};
			
			ans[i]+=solve(0,mn[1],mn[1]-m)+
					solve(1,mn[2],mn[2]-1)+
					solve(2,mx[1],mx[1]+m)+
					solve(3,mx[2],mx[2]+1);
			for(int j=0,nxt;j<4;++j){
				if(e[j][now]==1){
					if(rnk[nxt=id(px+d[j][0],py+d[j][1])] && rnk[nxt]<i){
						ans[i]+=(check(i,rnk[nxt]) && !tre.query(a[rnk[nxt]].lv,a[rnk[nxt]].lv,1,q,rt[!tmp][iid]));
					}else 
						ans[i]+=(fat[0].fnd(now)!=fat[0].fnd(nxt));
				}
			}
			
			--ans[i];
		}
		for(int i=1;i<=q;++i)write(ans[i],true);
		
	}
	
	return(0-0);
}