【题解】P7963 [NOIP2021] 棋局
棋子会将棋盘分开为若个部分，分裂过程不好维护。故先离线所有询问，将添加棋子改为删除棋子。
为了方便，我们略微更改棋子的等级，使其两两不同。
我们首先考虑 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();
}
}