题意：给定一个长度为 \(n\) 的排列 \(a\)，\(a_i \in [0,n-1]\)。你可以将这个排列进行循环移位，最小化 \(\sum_{i=1}^{n} \text{mex}_{j=1}^i a_j\) 的值。
首先我们可以先计算出最初情况下每一个 \(i\) 位置的 \(\text{mex}\) 值。这个序列一定是单调非严格递增的。
首先有一个比较显然的 \(\text{Trick}\)：\(\text{mex}_{j=1}^{i}a_j=\min_{j=i+1}^n a_j\)。
考虑将 \(a_1\) 循环移到第 \(n\) 位后会有什么影响。首先所有位置的 \(\text{mex}\) 值都要向左移动一位，第 \(n\) 位的值一定还是 \(n\)。对于现在 \(1\) 到 \(i-1\) 位上的值，因为第 \(n\) 位上的值变为了 \(a_1\)，而原来这些位置并没有算上 \(a_1\) 对他们的贡献，所以这些位置上的值都要和 \(a_1\) 取 \(\min\)。
上述过程可以用单调队列维护。具体的，每次循环移位需要执行以下几步操作：
-
将 \(a_1\)（队首）弹出。
-
将队尾大于 \(a_1\) 的数弹出，并在队尾插入相等数量的 \(a_1\)。
-
在队尾插入 \(n\)。
为了保证 \(O(n)\) 的时间复杂度，我们不用插入相同的数，而是直接记录这个数的数量即可。
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair <int,int> pii;
const int MAXN = 1e6 + 10;
typedef pair <int,int> pii;
deque <pii> q;
int t,n,a[MAXN],mex[MAXN],ans,sum;
signed main()
{
cin >> t;
while(t--)
{
while(!q.empty()) q.pop_front();
cin >> n;
for(int i = 1;i <= n;i++) cin >> a[i];
for(int i = 1;i <= n + 1;i++) mex[i] = 1e18;
mex[n] = n;
for(int i = n;i >= 1;i--) mex[i - 1] = min(mex[i],a[i]);
mex[0] = -1;ans = 0;
for(int i = 1;i <= n;i++)
{
if(mex[i] != mex[i - 1]) q.push_back(make_pair(mex[i],1));
else
{
pii tmp = make_pair(q.back().first,q.back().second + 1);
q.pop_back(),q.push_back(tmp);
}
ans += mex[i];
}
sum = ans;
for(int i = 1;i < n;i++)
{
sum -= q.front().first;
if(q.front().second == 1) q.pop_front();
else q.front().second--;
int num = 0;
while(!q.empty() && q.back().first > a[i])
{
sum -= q.back().first * q.back().second;
num += q.back().second;
q.pop_back();
}
sum += n,sum += num * a[i];
q.push_back(make_pair(a[i],num));
q.push_back(make_pair(n,1));
ans = max(ans,sum);
}
cout << ans << endl;
}
return 0;
}