CF1368G - Shifting Dominoes

题目大意

给定一个被$1\times 2$的骨牌（横向或者竖向）铺满的方格图

现在可以拿走一个骨牌，之后任意一个骨牌可以沿着其放置方向左右移动至多一步

求最终两个空位所在不同位置的方案数


分析

观察一个空位的移动

如果上/下/左/右边是一条骨牌，则可以移动到该骨牌所在的上/下/左/右边方格

将这个移动方式构成一个有向图（当然忽略反复横跳的情况）

大胆猜测此时你会发现它是 两片外向树森林，下面说明三个充分条件

1.跳跃的过程为$(x,y)\rightarrow (x\pm 2,y\pm 2)$，显然$x+y$的奇偶性不变，故可以黑白染色分为两部分

2.一个点至多有一条入边：一个点的入边只能来自其所在骨牌的另一边

3.图中不存在环：

假设构成了一个环，此时这些边对应的骨牌围成一个不规则的环

从环的某一个角出发，向四周走，发现其余所有点总能完成一一匹配

也就是说，环内部包含的点个数为奇数，显然不存在这样的覆盖方案


答案计算

考虑移除一张骨牌生成两个点$(x,y)$，两个点分属于两片森林，并且可以向下走

不妨求出森林的$\text{dfs}$序，此时问题变成了一个二维空间矩形覆盖问题

可以扫描线+线段树解决

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
const int N=2e5+10;

int n,m,d;
string s[N];
int I(int x,int y){ return (x-1)*m+y; }
ll ans;

vector <int> G[N];
int col(int u){ return ((u-1)%m+(u-1)/m)&1; }

void Link(int u,int v){ G[u].pb(v),ind[v]++; }
int ind[N],L[N],R[N],dfn;
void dfs(int u,int f){
	L[u]=++dfn;
	for(int v:G[u]) if(v!=f) dfs(v,u);
	R[u]=dfn;
}

// 线段树维护扫描过程中第二维未被覆盖的点个数
struct Node{
	int mi,x;
	Node operator + (const Node _) const {
		Node res;
		res.mi=min(mi,_.mi),res.x=0;
		if(mi==res.mi) res.x+=x;
		if(_.mi==res.mi) res.x+=_.x;
		return res;
	}
} tr[N<<2];
int t[N<<2];
void Down(int p){
	if(!t[p]) return;
	rep(i,p<<1,i+1) t[i]+=t[p],tr[i].mi+=t[p];
	t[p]=0;
}
void Upd(int p,int l,int r,int ql,int qr,int x){
	if(ql<=l && r<=qr) {
		t[p]+=x,tr[p].mi+=x;
		return;
	}
	Down(p);
	int mid=(l+r)>>1;
	if(ql<=mid) Upd(p<<1,l,mid,ql,qr,x);
	if(qr>mid) Upd(p<<1|1,mid+1,r,ql,qr,x);
	tr[p]=tr[p<<1]+tr[p<<1|1];
}

struct Update{
	int p,l,r,x;
	bool operator < (const Update __) const { return p<__.p; }
} U[N*2];
int C;

void Add(int x,int y){
	if(col(x)) swap(x,y);
	U[++C]=(Update){L[x],L[y],R[y],1};
	U[++C]=(Update){R[x]+1,L[y],R[y],-1};
}
void Build(int p,int l,int r){
	tr[p]=(Node){0,r-l+1};
	if(l==r) return;
	int mid=(l+r)>>1;
	Build(p<<1,l,mid),Build(p<<1|1,mid+1,r);
}

int main(){
	n=rd(),m=rd();
	rep(i,1,n) {
		cin>>s[i];
		rep(j,1,m) {
			if(s[i][j-1]=='U') if(i>1) Link(I(i-1,j),I(i+1,j));
			if(s[i][j-1]=='D') if(i<n) Link(I(i+1,j),I(i-1,j));
			if(s[i][j-1]=='L') if(j>1) Link(I(i,j-1),I(i,j+1));
			if(s[i][j-1]=='R') if(j<m) Link(I(i,j+1),I(i,j-1));
		}
	}
    // 获得dfs序
	rep(i,1,n*m) if(!ind[i]) dfs(i,0);
	rep(i,1,n) {
		rep(j,1,m) {
			if(s[i][j-1]=='U') Add(I(i,j),I(i+1,j));
			if(s[i][j-1]=='L') Add(I(i,j),I(i,j+1));
		}
	}
	Build(1,1,dfn);
	sort(U+1,U+C+1);
	int p=1;
	rep(i,1,dfn) {
		while(p<=C && U[p].p<=i) Upd(1,1,dfn,U[p].l,U[p].r,U[p].x),p++;
		int c=dfn-(tr[1].mi==0?tr[1].x:0);
		ans+=c;
	}
	printf("%lld\n",ans);
}