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";
}