CF1876D Lexichromatography
题目链接：https://codeforces.com/problemset/problem/1876/D
题意
给一个 $n$ 个数的数组 $a$ 染色，每个元素被染为红色或蓝色。求满足下面两个条件的染色方案数：
- 将蓝色和红色的数分别取出成为两个数列，则蓝色序列字典序小于红色序列。
- 任意一个子数组中，任意一个数 $x$ 被染色为蓝色和红色的次数相差不大于 $1$。
解法（官解）
首先分析第二个条件，不难发现它等价于条件“任意一个数 $x$ 被交替染色”。则任意一个数第一次出现时的颜色决定了之后所有出现的颜色，因此满足第二个条件的方案数为 $2^c$ （$c$ 为数组中不同元素的个数）。
下面在满足第二个条件的前提下讨论第一个条件。对于任意一个染色方案，将染色对调，仍然满足第二个条件；因此“蓝色序列字典序小于红色序列”和反之的方案数有一一对应关系。由于字典序是全序，答案就等于 $\dfrac{2^c - equal}{2}$，$equal$ 为“蓝色序列字典序等于红色序列”，即两序列相同的方案数。
下面考虑如何计算 $equal$。
首先构造一种两序列相同的方案。对每次加入一个数，模拟两个序列的变化：
- 如果这个数不是待匹配的数，将这个数放在更长的序列中，作为待匹配的数（否则，若将其放在较短的序列中，它一定无法与对应的数匹配）。
- 否则将其放在较短序列中，尝试与较长序列对应的数匹配。若匹配失败，说明不存在合法的构造。
考虑如何对合法构造进行计数。在上面的构造中，我们始终把待匹配的数放在更长的序列中。但当两个序列的长度相等时，将数放在两个序列均可以（当然，若这个数在前面存在，只能放在上一次出现的相反序列中）。因此，以两序列长度相同为分界点，对数组分段；构造一个图，每一段与其中出现过的数字连边，就有 $equal = 2^d$（$d$ 为连通分量数）。
代码实现（C++)
constexpr int M = 200000;
void solve() {
int n;
cin >> n;
vector<int> vis(M + 1), a, b;
UnionFindSet ufs(n + M + 1);
int cnt = 0, times = 0, block_idx = 1;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (!vis[x]++) { cnt++, times++; }
((vis[x] % 2) ? a : b).push_back(x);
times -= ufs.merge(block_idx + M, x);
if (a.size() == b.size()) times++, block_idx++;
}
Z res = Z(2).pow(cnt);
if (a == b) { res -= Z(2).pow(times); }
cout << res / 2 << "\n";
}