Codeforces Round #767 (Div. 2)

呜，一学期都没打cf，久而久之变得生疏和害怕了，寒假第一场cf就如此...惨烈，不过也是随着补题才有提升嘛。

C. Meximum Array

mex...之前只在博弈论之类的见到过...没自己实现过呜。

这题很重要的一点是对于固定起点的一系列前缀求mex数组的话，这个数组是单调不减的，并且上升速度不会超过1/1

也就是说，我们设当前位置作为末尾的数组的mex值为 j 的话，每次移动位置后，只要将原数组当前位置的值在mark数组中做好标记，然后让 j  一直++直到遇到未标记的位置，这个 j 就是当前位置作为末尾的数组的mex值。

以上是线性时间复杂度求前缀mex的办法，此题还有个关键是要记录mex数组第一次达到最大值的位置，我一开始想的是，每次增长就记录一下位置，最后自然得到结果。但是这个方法实际上复杂度过高了，因为很有可能2*10⁵的数组只要4位mex就达到了最大（test 2），O(n²)中每次后面的计算都是多余的，因为每个都计算了n次。

这时候灵机一动发现，只要我提前用O(n)算出后缀的mex，那么第一次达到最大也就只要比较 j 等于后缀的mex就行了。注意这里的后缀的开头是指上一次循环中记录的第一次最大位置，也是这次的开始位置（即使在补题时还是大意吃了发WA（悲））。

AC代码：

#include 
#define ll long long
#define F freopen("in.txt", "r", stdin)
using namespace std;
int num[200005], mrk[200005], mex2[200005];
int main()
{
    //F;
    int t;
    cin >> t;
    while (t--)
    {
        vector<int> ans;
        int n;
        cin >> n;
        int x = 1;
        for (int i = 1; i <= n; i++)
            cin >> num[i];
        int j2 = 0;
        for (int i = n; i > 0; i--)
        {
            mrk[num[i]] = true;
            while (mrk[j2])
                j2++;
            mex2[i] = j2;
        }
        memset(mrk, 0, sizeof(mrk));
        while (x <= n)
        {
            //cout << "x:" << x << " ";
            int j = 0, maxj = 0;
            for (int i = x; i <= n; i++)
            {
                mrk[num[i]] = true;
                while (mrk[j])
                    j++;
                if (j == mex2[x] || i == n)
                {
                    maxj = j;
                    x = i + 1;
                    break;
                }
            }
            ans.push_back(maxj);
            memset(mrk, 0, sizeof(mrk));
        }
        int st = ans.size();
        cout << st << endl;
        for (int i = 0; i < st; i++)
            cout << ans[i] << (i == st - 1 ? "" : " ");
        cout << endl;
        memset(mex2, 0, sizeof(mex2));
    }
    return 0;
}