(omg fz blog!) i guess you can binary search on a segment tree that have vec[i] as indices and 1 as value, the condition of the bs would be if(m-i+1 < query(i, m)) go left else go right, this should work, so lg^2(n) per query and lg(n) updates, if you hate segment tree (*get some help*) ig you can do prefix sum + coordinate compression but that's confusing to implement, interested if a better solution is possible!

If there are insertion, deletion operations on our vector:

Let n = upper bound on answer.

We can maintain a set of numbers not present in the given vector, let's denote it as S. Finding the answer will be the same as finding the lowest number in S, not less than X. So the time complexity will be O(nlog(n))

If there are no insertion, deletion operations on our vector:

Let's denote the given vector as v. Let's sort v and remove duplicates, and for each x in v, precalculate answer if X = x. If X is present in v, output the value that we precalculated, otherwise output X. To precalculate answer for each x in v, we can do the following: if x+1 is present in v, then answer for x will be equal to answer for x+1, otherwise x+1 will be the answer.

Time complexity will be O((q+N)log(N)), where q is the number of queries and N is the number of elements in vector.

Build a weight segment tree which records the number of the elements that do not exist in the vector, binary search on the segment tree to find the first location that its prefix sum of the number is not $$$0$$$.

The time complexity is $$$O((n+q)\log W)$$$.

subtract x from everything and deal it like mex

lets say you have 4, 5, 6, 9, 10 in your data

we will store in map {4, 6} {9, 10}

now lets say you want >= missing key for 9

so we query <= 9 which is 9 itself in the map

then the value of it is 10, hence all numbers from 9 to 10 are present so 11 is the missing one

 map<int, int> interval;
    unordered_map<int, int, chash> fmap;

    void insert(int value) {
        fmap[value]++;
        if (fmap[value] > 1) return;

        int l = floor(interval, value);
        if (l != -1 && interval[l] >= value - 1)
            interval[l] = max(interval[l], value);
        else {
            l = value;
            interval[l] = l;
        }

        if (interval.count(interval[l] + 1)) {
            int val = interval[l] + 1;
            interval[l] = interval[interval[l] + 1];
            interval.erase(val);
        }
    }

    void erase(int value) {
        fmap[value]--;
        if (fmap[value] > 0) return;

        int l = floor(interval, value);
        if (l == value) {
            interval[value + 1] = interval[l];
            interval.erase(value);
        } else {
            interval[value + 1] = interval[l];
            interval[l] = value - 1;
        }
    }

    int query(int value) {
        int f = floor(interval, value);
        if (f == -1) return value;
        return max(interval[f] + 1, value);
    }

i have created a problem on polygon refer the first question of this mashup https://codeforces.me/contestInvitation/0c55b0f44793caa990ef4f0bf1d13711ef2481d1

I assume that u will have repetitive queries about the MEX of the array that you have. The naïve approach of recalculating MEX each time is what's getting a TLE since it's O(n^2). We can easily avoid "recalculating" by keeping in mind that adding elements will never decrease the MEX. So we keep a separate array of Boolean numbers, and a counter that moves forward while the number it's at is true in the array. and even though this is going to be implemented using a "while" loop nested in your for loop, this nested loop will visit each value at most once, so the overall complexity is going to be O(n).

set mex = x, sort the vector (dont need to if its a set), then increment mex while mex is found in the vector/set