本文章遵守知识共享协议 CC-BY-NC-SA，同步发表于洛谷题解区，转载时须在文章的任一位置附上原文链接和作者署名（rickyxrc）。推荐在我的个人博客阅读。
人生第一道 3200！
题面大意
有一个已经铺满多米诺骨牌的棋盘，你可以拿下来一块骨牌，并将剩下的骨牌移动来填补空位，但是每个骨牌只能移动最多一位，求可能得到的本质不同的方案数。
解题思路
我们首先这么想：一个骨牌滑动一步，相当于对应的空位移动两步。
然后我们不难发现两个相邻的点，其 xy 坐标奇偶性是不同的，在坐标变化 2 之后奇偶性仍然是不同的。
这就代表着两个点是不会走到相同的地方的，我们可以分开计算。
此时我们参考建图的思路，对每个点（作为空位时）向能到达的点连边。
容易证明，建出来的图一定是一个森林，因为图中不存在环（没有方案可以移动骨牌使得恰好回到原位）且每个点的出度最大为 1。
每个点能到达的点数量就是子树大小，两个点将其相乘即可。
但是可能会出现重复统计的问题（不是两个点重复，而是不同的点对得到了相同的清空），对此我们将每组答案看作一个长宽分别为两颗子树大小的矩形，左下角坐标是两个点的 dfn。
为什么这样建模呢？因为在一棵子树中，所有 dfs 是连续的，所以这个矩形就可以包含所有答案的情况。
最后使用扫描线求解即可。
#include <stdio.h>
#include <vector>
#include <algorithm>
#define maxn 1000007
typedef long long i64;
std::vector<i64> edge[maxn];
char mp[maxn];
i64 n, m;
char ch;
inline i64 hsh(i64 x, i64 y) { return (x - 1) * m + y; }
i64 dfn[maxn], size[maxn], dfncnt, ids[maxn], idcnt, indeg[maxn];
i64 res;
std::vector<std::pair<std::pair<i64, i64>, std::pair<i64, i64>>> points;
void dfs(i64 index)
{
size[index] = 1;
dfn[index] = ++dfncnt;
for (auto u : edge[index])
dfs(u),
size[index] += size[u];
}
#define ls (index << 1)
#define rs (ls | 1)
#define mid ((l + r) >> 1)
i64 xtmp[maxn << 2];
struct stree
{
i64 data, lazy, l, r;
} trees[maxn << 2];
struct sq
{
i64 x, y1, y2, vl;
} seq[maxn << 2];
inline bool cmp(sq a, sq b)
{
return a.x < b.x;
}
void pushup(i64 index)
{
if (trees[index].lazy > 0)
trees[index].data = trees[index].r - trees[index].l;
else
trees[index].data = trees[ls].data + trees[rs].data;
}
void build(i64 index, i64 l, i64 r);
inline i64 min(i64 a, i64 b);
inline i64 max(i64 a, i64 b);
void update(i64 index, i64 y1, i64 y2, i64 vl);
i64 linecnt;
void add_line(i64 xxx1, i64 yyy1, i64 xxx2, i64 yyy2, i64 _sum)
{
seq[++linecnt].x = xxx1;
seq[linecnt + _sum].x = xxx2;
seq[linecnt].y1 = seq[linecnt + _sum].y1 = yyy1;
seq[linecnt].y2 = seq[linecnt + _sum].y2 = yyy2;
seq[linecnt].vl = 1;
seq[linecnt + _sum].vl = -1;
xtmp[linecnt] = yyy1;
xtmp[linecnt + _sum] = yyy2;
}
i64 a, b, l1, l2, r1, r2, siz_;
int main()
{
scanf("%d%d", &n, &m);
for (i64 i = 1; i <= n; i++)
for (i64 j = 1; j <= m; j++)
{
do
{
ch = getchar();
} while (ch != 'U' && ch != 'D' && ch != 'L' && ch != 'R');
mp[hsh(i, j)] = ch;
}
for (i64 i = 1; i <= n; i++)
for (i64 j = 1; j <= m; j++)
{
if (i + 2 <= n && mp[hsh(i + 1, j)] == 'U' && mp[hsh(i + 2, j)] == 'D')
indeg[hsh(i + 2, j)]++,
edge[hsh(i, j)].push_back(hsh(i + 2, j));
if (i - 2 >= 1 && mp[hsh(i - 1, j)] == 'D' && mp[hsh(i - 2, j)] == 'U')
indeg[hsh(i - 2, j)]++,
edge[hsh(i, j)].push_back(hsh(i - 2, j));
if (j + 2 <= m && mp[hsh(i, j + 1)] == 'L' && mp[hsh(i, j + 2)] == 'R')
indeg[hsh(i, j + 2)]++,
edge[hsh(i, j)].push_back(hsh(i, j + 2));
if (j - 2 >= 1 && mp[hsh(i, j - 1)] == 'R' && mp[hsh(i, j - 2)] == 'L')
indeg[hsh(i, j - 2)]++,
edge[hsh(i, j)].push_back(hsh(i, j - 2));
if (mp[hsh(i, j)] == 'L')
points.push_back({{i, j}, {i, j + 1}});
if (mp[hsh(i, j)] == 'U')
points.push_back({{i, j}, {i + 1, j}});
}
for (i64 i = 1; i <= n; i++)
for (i64 j = 1; j <= m; j++)
if (!indeg[hsh(i, j)])
dfs(hsh(i, j));
for (auto u : points)
{
a = hsh(u.first.first, u.first.second), b = hsh(u.second.first, u.second.second);
l1 = dfn[a], r1 = dfn[a] + size[a];
l2 = dfn[b], r2 = dfn[b] + size[b];
if ((u.first.first + u.first.second) & 1)
add_line(l2, l1, r2, r1, (n * m) >> 1);
else
add_line(l1, l2, r1, r2, (n * m) >> 1);
}
siz_ = points.size();
std::sort(xtmp + 1, xtmp + 2 * siz_ + 1);
std::sort(seq + 1, seq + 2 * siz_ + 1, cmp);
build(1, 1, 2 * siz_);
update(1, seq[1].y1, seq[1].y2, seq[1].vl);
for (i64 i = 2; i <= 2 * siz_; i++)
{
res += 1ll * (seq[i].x - seq[i - 1].x) * trees[1].data;
update(1, seq[i].y1, seq[i].y2, seq[i].vl);
}
printf("%lld", res);
return 0;
}