D. Cyclic MEX 题解

题意简述

给定一个 $0 \sim n-1$ 的排列 $p$。

对于一个数组 $a$，定义它的代价为：

$$\sum_{i=1}^{n} \operatorname{mex}([a_1,a_2,\dots,a_i]) $$

现在我们可以对排列做任意循环移位，要求所有循环移位中代价的最大值。

核心观察

先固定一个当前排列：

$$a_1,a_2,\dots,a_n$$

记它的前缀 mex 序列为：

$$m_1,m_2,\dots,m_n$$

其中：

$$m_i=\operatorname{mex}([a_1,a_2,\dots,a_i])$$

如果我们把整个排列循环左移一位，那么会发生什么？

也就是从：

$$a_1,a_2,\dots,a_n$$

变成：

$$a_2,a_3,\dots,a_n,a_1$$

设被移走的首元素是 $a_1$，那么新的前缀 mex 序列可以由原序列直接推出：

$1$．第一个前缀 mex 被删掉

因为左移后，长度为 $1$ 的前缀不再是原来的 $[a_1]$，所以原来的 $m_1$ 直接从序列前端消失。

$2$．所有小于 $a_1$ 的前缀 mex 不变

如果某个前缀 mex 为 $x<a_1$，说明：

• $0 \sim x-1$ 都已经出现；
• $x$ 还没有出现。

删掉 $a_1$ 不会影响到 $x$ 仍然缺失，所以这个 mex 还是 $x$。

$3$．所有大于 $a_1$ 的前缀 mex 都会变成 $a_1$

如果某个前缀 mex 为 $x>a_1$，那么说明：

• $0 \sim x-1$ 全都出现了；
• 特别地，$a_1<x$，因此 $a_1$ 一定已经在这个前缀里。

而左移后，原来的前缀都失去了这个最前面的 $a_1$，所以现在最小缺失值就变成了 $a_1$。

于是这些 mex 全部会统一变成：

$$a_1$$

$4$．最后会新加入一个 $n$

因为整个数组始终是一个排列，所以完整长度的整个数组一定包含了：

$$0,1,2,\dots,n-1$$

因此整个数组的 mex 永远都是：

$$n$$

所以左移一次后，新的前缀 mex 序列就是：

• 删掉最前面的一个值；
• 保留所有小于 $a_1$ 的值不变；
• 把所有大于 $a_1$ 的值全部改成 $a_1$；
• 最后再补上一个 $n$。

为什么可以用双端队列维护

注意前缀 mex 序列本身一定是单调不降的。

因为随着前缀变长，只会多出元素，不会少元素，所以 mex 不可能变小。

于是我们可以把这个序列压缩存储成若干段：

$$(值,\ 该值出现次数)$$

例如把：

$$0,0,0,2,2,5,5,5$$

压成：

$$(0,3),(2,2),(5,3)$$

这样每次循环左移时，就可以直接在压缩后的序列上模拟变化。

如何维护这条压缩序列

设当前被移走的首元素为：

$$x=a_i$$

那么操作过程如下：

$1$．弹出队首一个 mex

对应“第一个前缀 mex 被删掉”。

如果队首这一段的出现次数减到 $0$，就把整段弹出。

$2$．从队尾开始，把所有值大于等于 $x$ 的段合并

根据上面的结论，所有原来大于 $x$ 的 mex 都要变成 $x$。

而由于前缀 mex 序列单调不降，这些值一定都集中在队尾。

所以我们从队尾不断弹出这些段，把它们的出现次数累加起来，最后统一变成一段：

$$(x,\text{合并后的总次数})$$

代码中写成：

pair<int, int> me = {a[i], 0};
while (!dq.empty() && dq.back().first >= a[i])
{
    sum -= dq.back().first * dq.back().second;
    me.second += dq.back().second;
    dq.pop_back();
}
dq.push_back(me);
sum = sum + me.first * me.second;

这里写的是 $\ge a_i$，实际上由于所有前缀都包含当前首元素 $a_i$，所以 mex 不可能恰好等于 $a_i$，写成 $\ge$ 只是更方便实现。

$3$．在队尾补一个 $(n,1)$

对应“整个数组的 mex 恒为 $n$”。

dq.push_back({n, 1});
sum += n;

$4$．维护答案

设当前所有前缀 mex 的总和为 sum，那么每做完一次左移，就更新：

ans = max(ans, sum);

初始前缀 mex 序列如何求

先对原排列从左到右扫描。

用数组 f[x] 统计每个值是否出现过，同时维护当前 mex：

vector<int> f(n + 1);
int mex = 0;
for (int i = 1; i <= n; ++i)
{
    f[a[i]]++;
    while (f[mex])
    {
        mex++;
    }
    dq.push_back({mex, 1});
    sum += mex;
}

这样就得到了最初的前缀 mex 序列。由于这里先按单个元素入队，后面在模拟过程中自然会进行压缩合并。

正确性说明

性质 $1$

对于任意一个排列，前缀 mex 序列是单调不降的。

因此可以用若干个相同值的连续段来压缩表示。

性质 $2$

一次循环左移后：

• 原序列首项消失；
• 所有小于首元素的 mex 不变；
• 所有大于首元素的 mex 全部变成首元素；
• 末尾新增一个 $n$。

这与代码中对双端队列的修改完全一致。

性质 $3$

代码中的 sum 始终等于当前这个循环移位对应的所有前缀 mex 之和。

因此每次更新：

$$ans=\max(ans,sum)$$

最终得到的就是所有循环移位中的最大代价。

综上，算法正确。

复杂度分析

每个前缀 mex 段在双端队列中至多被插入一次、弹出一次。

因此虽然看起来每次都会在队尾反复弹出，但所有弹出操作的总次数是线性的。

整个算法对每组测试数据的时间复杂度为：

$$O(n)$$

空间复杂度为：

$$O(n)$$

而所有测试数据中 $n$ 的总和不超过：

$$10^6$$

所以能够通过。

参考代码

#include <bits/stdc++.h> 

#define int long long

using namespace std;

int32_t main()
{
	cin.tie(nullptr)->sync_with_stdio(false);
	int q;
	cin >> q;
	while (q--)
	{
		int n;
		cin >> n;
		vector<int> a(n + 1);
		for (int i = 1; i <= n; ++i)
		{
			cin >> a[i];
		}
		deque<pair<int, int>> dq;
		vector<int> f(n + 1);
		int mex = 0;
		int sum = 0;
		for (int i = 1; i <= n; ++i)
		{
			f[a[i]]++;
			while (f[mex])
			{
				mex++;
			}
			dq.push_back({mex, 1});
			sum += mex;
		}
		int ans = sum;
		for (int i = 1; i < n; ++i)
		{
			pair<int, int> me = {a[i], 0};
			sum -= dq.front().first;
			dq.front().second--;
			if (dq.front().second == 0)
			{
				dq.pop_front();
			}
			while (!dq.empty() && dq.back().first >= a[i])
			{
				sum -= dq.back().first * dq.back().second;
				me.second += dq.back().second;
				dq.pop_back();
			}
			dq.push_back(me);
			sum = sum + me.first * me.second;
			dq.push_back({n, 1});
			sum += n;
			ans = max(ans, sum);
		}
		cout << ans << '\n';
	}
}