先放一点上来，剩下的慢慢更。
ビルの飾り付け 4 / Building 4
不难想到一个 $\mathcal{O}(n^2)$ 的 DP：设 $f_{i, j, 0/1}$ 表示前 $i$ 个数选了 $j$ 个 A，最后一个是 A/B 是否可行，转移显然。最后逆序构造方案即可。
可以发现对于某个 $i, 0/1$，为真的 $j$ 一定是一段区间，因此我们只需要维护这段区间，即可去掉 $j$ 一维。这样子复杂度变为 $\mathcal{O}(n)$。
美味しい美味しいハンバーグ / Hamburg Steak
咕咕咕
掃除 / Sweeping
先考虑只有 V 操作和查询的情况，每次相当于把一段横坐标区间的纵坐标取 $\max$，线段树维护即可。
然后考虑加入 H 操作。可以发现，设之前的 V 操作影响到的最大坐标为 $x$，当前 H 操作能影响到的横坐标范围为 $(x, n - l]$，因为更左边的都被扫走了。
可以发现这样子两维就互不影响了（？），因此可以用两棵线段树维护。
最后再考虑加入插入操作。对于每个询问，我们把对应的插入到它的这段区间丢到线段树上，拆分为 $\mathcal{O}(\log Q)$ 个区间，然后计算操作对每段区间的贡献即可。
カメレオンの恋 / Chameleon’s Love
先考虑知道性别的情况。
设 $S$ 是另一侧的某个集合，考虑询问 $\{u\}\cup S$ 可能出现的结果。如果 $S$ 中有喜欢 $u$ 的 / $u$ 喜欢的 / 与 $u$ 同色的变色龙，那么结果为 $\lvert S\rvert$。这样子就可以通过至多 $3$ 次二分找到和 $u$ 有特殊关系的点。
显然 $u$ 有特殊关系的点只可能有 $1$ 个或 $3$ 个。如果为 $1$ 个，那一定是同色的；否则我们可以每次询问其中的两个和 $u$ 来找到 $u$ 喜欢的那一只。
在确定所有喜欢的关系后，剩下的就是同色的了。
现在考虑不知道性别的情况，此时的主要问题在于分离二分图两侧的点集。
但事实上我们并不需要分离两侧的点集，我们只需要让 $S$ 内部没有特殊关系即可。于是我们把之前已经确定的特殊关系拿出来二分图染色，对两侧的点分别跑一遍即可。
ジョイッターで友達をつくろう / Making Friends on Joitter is Fun
可以发现一个大小为 $s$、入边数为 $k$ 的强连通分量的贡献为 $s(s-1)+sk$，于是我们只需要动态维护这个东西。
用并查集维护每个点所在的强连通分量，用 set 维护每个强连通分量的入边、出边，合并时只需要讨论一下几种情况即可。
需要注意的是，合并两个强连通分量后可能会引起新的合并，需要开一个队列存下所有会合并的强连通分量对。
最古の遺跡 3 / Ruins 3
咕咕咕
星座 3 / Constellation 3
从下往上扫描，并对每个纵坐标维护其下方选了的且与它冲突星星的权值和。
如果它的权值比这个权值和小，则我们会删去它，否则我们会删去下面选了的星星。
用树状数组维护，并用并查集维护左、右两边第一个白色格子即可。
収穫 / Harvest
咕咕咕
迷い猫 / Stray Cat
咕咕咕
首都 / Capital City
考虑建这样一张图：如果所有颜色为 $i$ 的点构成的极小连通块中有颜色为 $j$ 的点，则从 $i$ 向 $j$ 连边。
一条边 $(u,v)$ 的实际意义就是，如果想让 $u$ 连通，则必须把 $u,v$ 合并。
一个强连通分量显然需要合并 $sz-1$ 次，这样子可以缩点成一张 DAG，那么一条到出度为 $0$ 的点的路径是合法的。这样子最短的路径一定是某个出度为 $0$ 的点到自己，直接枚举这样的点，求 $sz-1$ 的最小值即可。
现在考虑建图的问题。对于每种颜色，求出颜色为它的点的 LCA，极小连通块即为这些点到 LCA 的链并。不妨让每个点都向其颜色连边，这样子只需要一种颜色向若干条链上的点连边，树剖+线段树优化即可。
伝説の団子職人 / Legendary Dango Maker
考虑随机调整。我们每次随机一个 W，然后找到以其为中心的一串团子，并进行讨论：
- 如果这串团子与已有的不冲突，则直接放上去；
- 如果这串团子与已有的恰好一串冲突，则以 $\frac{1}{2}$ 的概率替换掉之前的那一串。
这样子有可能在局部最优解中出不来，所以最好多开几个一起跑。如果 RP 还行的话可以在 $20$ 分钟内跑出任意一个点。
一个小小的优化：只随机那些有可能组成合法团子串的 W，这样子在某些点上可以快许多。
// ====================================
// author: M_sea
// website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;
int read() {
int X = 0, w = 1; char c = getchar();
while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
return X * w;
}
const int N = 500 + 10;
const int LIM = 47220; // Z
const int dx[4] = {1, 0, 1, 1};
const int dy[4] = {0, 1, 1, -1};
mt19937 rnd(time(0));
int n, m, vis[N][N], bld[N][N];
pair<int, int> bl[N][N];
char s[N][N], ans[N][N];
vector<pair<int, int>> white_dango;
bool check(char a, char b, char c) {
return (a == 'P' && b == 'W' && c == 'G') || (a == 'G' && b == 'W' && c == 'P');
}
int findd(int x, int y) {
int p[4] = {0, 1, 2, 3};
shuffle(p, p + 4, rnd);
for (int i = 0; i < 4; ++i) {
int d = p[i], x1 = x - dx[d], y1 = y - dy[d], x2 = x + dx[d], y2 = y + dy[d];
if (x1 < 1 || x1 > n || y1 < 1 || y1 > m || x2 < 1 || x2 > n || y2 < 1 || y2 > m) continue;
if (check(s[x1][y1], s[x][y], s[x2][y2])) return d;
}
return -1;
}
int main() {
n = read(), m = read();
for (int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
if (s[i][j] == 'W' && findd(i, j) >= 0) white_dango.emplace_back(i, j);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
ans[i][j] = s[i][j];
int cnt = 0;
while (cnt < LIM) {
int p = rnd() % white_dango.size();
int x = white_dango[p].first, y = white_dango[p].second;
int d = findd(x, y);
if (d < 0) continue;
int x1 = x - dx[d], y1 = y - dy[d], x2 = x + dx[d], y2 = y + dy[d];
if (!vis[x1][y1] && !vis[x][y] && !vis[x2][y2]) {
vis[x1][y1] = vis[x][y] = vis[x2][y2] = 1;
bl[x1][y1] = bl[x][y] = bl[x2][y2] = make_pair(x, y);
bld[x1][y1] = bld[x][y] = bld[x2][y2] = d;
ans[x][y] = "|-\\/"[d], ++cnt;
debug("cnt = %d\n", cnt);
} else if (vis[x1][y1] + vis[x][y] + vis[x2][y2] == 1 && (rnd() & 1)) {
int X, Y, D;
if (vis[x1][y1]) X = bl[x1][y1].first, Y = bl[x1][y1].second, D = bld[x1][y1];
else if (vis[x][y]) X = bl[x][y].first, Y = bl[x][y].second, D = bld[x][y];
else X = bl[x2][y2].first, Y = bl[x2][y2].second, D = bld[x2][y2];
int X1 = X - dx[D], Y1 = Y - dy[D], X2 = X + dx[D], Y2 = Y + dy[D];
vis[X1][Y1] = vis[X][Y] = vis[X2][Y2] = 0;
ans[X][Y] = s[X][Y];
vis[x1][y1] = vis[x][y] = vis[x2][y2] = 1;
bl[x1][y1] = bl[x][y] = bl[x2][y2] = make_pair(x, y);
bld[x1][y1] = bld[x][y] = bld[x2][y2] = d;
ans[x][y] = "|-\\/"[d];
}
}
debug("ans = %d\n", cnt);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) putchar(ans[i][j]);
puts("");
}
return 0;
}治療計画 / Treatment Project
先考虑一个 DP。设 $dp_i$ 表示 $t_i$ 时刻 $[1, r_i]$ 均已治愈的最小代价，$i$ 能转移到 $j$ 当且仅当 $r_i - l_j + 1 \geq \lvert t_i - t_j \rvert$。
可以发现转移类似于最短路，我们需要快速转移。
显然把绝对值拆掉。把所有计划按 $t_i$ 从小到大排序，用两棵线段树维护 $l_i-t_i$ 的最小值和 $l_i+t_i$ 的最小值，每次暴力在线段树上找到满足条件的点即可。找到之后，需要把线段树上这些点的权值改成 $+\infty$。
因为是点权，所以每个点只会被松弛一次，因此复杂度是对的。