Codeforces Round 915 (Div. 2) D. Cyclic MEX(数据结构，2000)

枚举环节维护mex的题

Problem - D - Codeforces

我们可以这样来看一次左移对前缀 mex 序列的影响：

1. 将第一个前缀 mex 弹出。

2. 对于值小于 p1 的那些前缀 mex，保持不变。

3. 对于值大于 p1 的那些前缀 mex，都变成 p1。

4. 在序列末尾追加一个值为 n 的 mex。

为了高效处理，我们不用存下整个前缀 mex 序列，而是对相同的 mex 值做“值—频次”压缩（即记录每个 mex 值及其连续出现的次数）。然后用双端队列（deque）来模拟上述四个步骤。由于每次操作都会减少“潜在”未处理的元素数量，整个模拟只需线性时间，复杂度为 O(n)。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5 + 10;
const int mod = 998244353;
#define pii pair<int, int>
#define lowbit(x) (x & (-x))
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    deque<pii> dq;
    int mex = 0;
    map<int, int> mp;
    int res = 0;
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        mp[a[i]]++;
        while (mp[mex])
            mex++;
        sum += mex;
        dq.push_back({mex, 1});
    }
    res = sum;
    // 左旋转变化：
    // mex>a[i]的，强制变为a[i]，其他mex值不变
    // 在dq中mex明显从左到右递增，我们只需要取右边满足mex>a[i]的mex更新dq即可
    for (int i = 0; i < n - 1; i++)
    {
        pii now = {a[i], 0};

        // 1) 删除原来的 M_1
        sum -= dq.front().first;
        dq.front().second--;
        if (dq.front().second == 0)
            dq.pop_front();

        // 2) 合并所有 ≥ x 的队尾段
        while (!dq.empty() && dq.back().first > a[i])
        {
            sum -= dq.back().first * dq.back().second;
            now.second += dq.back().second;
            dq.pop_back();
        }

        // 3) 把 (x, total_cnt) 放回队尾
        dq.push_back(now);
        sum += now.first * now.second;

        // 4) 末尾再加一个 mex=n
        dq.push_back({n, 1});
        sum += n;

        res = max(res, sum);
    }
    cout << res << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
}