No mex m#11792

No mex m (Editorial)

Problem Author:	Kostiantyn Denysov
Prepared by:	Kostiantyn Denysov, Maksym Shvedchenko
Editorial by:	Kostiantyn Denysov

How to solve the problem for fixed value of $m > 0$ m > 0 (for $m = 0$ m=0 the answer is just the number of nonzero elements)? At first, let's mention that if we do change the number then it is optimal to change its value to $m$ , because if on the segment there is a number $m$ then its mex can't be exactly $m$ .

Then the following greedy works:

we will through our array from left to right and support set S or current elements (it is empty at first);
suppose we are considering element $a_{i}$ a_i;
if $a_{i} = m$ a_i=m then we set $S = \emptyset$ S=\emptyset, because we after adding this element we do not care what elements were before it;
otherwise insert $a_{i}$ a_i to the set $S$ and calculate its mex. If mex is equal to $m$ then we need to change current element to $m$ and clear the set (we do one changing operation here).

If we implement it accurately, we can solve the problem in $O (n)$ for fixed $m$ . So total $O (n^{2})$ O(n^2) solution which is pretty slow, but can be optimized.

But we can optimize it further. How many operations of changing the elements we will do in total for all $m$ ? Let $an s_{k}$ ans_k — be the answer (number of operations needed) for $m = k$ m=k. It turns out that $\sum_{i = 1}^{n} an s_{k} \leq n$ \sum_{i=1}^n ans_k \le n. Why?

Let $c n t_{i}$ cnt_i — be the amount of element $i$ in our array. Let's bound answer for fixed $k$ . When we do the operation? When in our set $S$ , there are elements $0$ , $1$ , $\dots$ , $k - 1$ k-1, and then we clear the set. That means that we can't do more operations than the minimal amount of $c n t_{0}$ cnt_0, $c n t_{1}$ cnt_1, $\dots$ , $c n t_{k - 1}$ cnt_{k-1}. So $an s_{k} \leq min (c n t_{0}, c n t_{1}, \dots, c n t_{k - 1})$ ans_k \le \min(cnt_0, cnt_1, \ldots, cnt_{k-1}).

Then $\sum_{i = 1}^{n} an s_{k} \leq \sum_{i = 1}^{n} min (c n t_{0}, c n t_{1}, \dots, c n t_{i - 1}) \leq \sum_{i = 1}^{n} c n t_{i - 1} \leq n$ \sum_{i=1}^n ans_k \le \sum_{i=1}^n \min(cnt_0, cnt_1, \ldots, cnt_{i-1}) \le \sum_{i=1}^n cnt_{i-1} \le n.

How to find those changing operations fast? While we go from left to right, we can support an array $n x t_{x}$ nxt_x — the minimal position $p os \geq i$ pos \ge i such that $a_{p os} = x$ a_{pos}=x (or ( $n + 1$ n+1) if none such position). By supporting this array we can find the next position where we need to do the operation by just finding $max (n x t_{0}, n x t_{1}, \dots, n x t_{k - 1})$ \max(nxt_0, nxt_1, \ldots, nxt_{k-1}) and also comparing it with $n x t_{k}$ nxt_k in order to understand where to go first (clear the set) or do a change operation and then clear. Finding maximum can be done efficiently with segment tree on fenwick tree, in this case.

Time complexity: $O (n lo g (n))$ O(n \log(n)).

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<class T>
using vec = vector<T>;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KoRoVa
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = -1, inf = 1000111222;




template <class T>
struct fenwick {
public:
    int n;
    vector <T> t; /// !!!


    fenwick (int n) : n(n) {
        t.assign(n, T(0));
    }

    inline void upd (int i, T x) {
        for (; i < n; i = i | (i + 1)) umax(t[i], x);
    }

    inline T max (int r) {
        T ans = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1) umax(ans, t[r]);
        return ans;
    }

};


int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);


    int n, m, l, r;
    cin >> n >> l >> r;
    vec<int> a(n);
    for (auto &i : a) cin >> i;
    vec<int> last(n, n);
    vec<int> ans(n + 1), pos(n + 1, n);
    for (int i = n - 1; i >= 0; i--) {
        last[i] = pos[a[i]];
        pos[a[i]] = i;
    }
    vec<vec<int>> have(n + 1);
    fenwick<int> t(n + 1);
    for (int i = 0; i <= n; i++) {
        have[0].pb(i);
        t.upd(i, pos[i]);
    }
    vec<int> now = pos;
    for (int i = 0; i < n; i++) {
        for (int x : have[i]) {
            int to = x == 0 ? i : t.max(x - 1);
            int nxt = now[x];
            if (to == n) {
                continue;
            }
            if (to < nxt) {
                ++ans[x];
                have[to + 1].pb(x);
            }
            else {
                have[nxt + 1].pb(x);
            }
        }
        t.upd(a[i], last[i]);
        now[a[i]] = last[i];
    }
    for (int i = l; i <= r; i++) {
        cout << ans[i] << ' ';
    }
    cout << '\n';

    return 0;
}

/*
KoRoVa!

 5 0 5
0 1 0 2 1
*/

C++