Range MEX queries offline in O(log n)

Revision en4, by one_autum_leaf, 2023-06-27 19:00:34

Consider the following problem : Your are given an array $$$a_1, a_2, ..., a_n$$$ and q queries of form $$$l r$$$. For each query you have to find the MEX of the array $$$a_l, a_{l+1}, ..., a_r$$$. The queries are offline.

One approach to the problem is discussed here.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct SegmentTree{
    int n;
    vector<int> tree;
    SegmentTree(int sz){
        n = 1;
        while(n < sz){
            n <<= 1;
        }
        tree.assign(2 * n, 0);
    }
    void set(int ind, int val){
        ind += n;
        tree[ind] = val;
        ind >>= 1;
        while(ind > 0){
            tree[ind] = min(tree[2 * ind], tree[2 * ind + 1]);
            ind >>= 1;
        }
    }
    int get(int x, int node = 1){
        // return the first index i, such that s[i] < x
        int ans = 1;
        while(ans < n){
            ans <<= 1;
            if(tree[ans] >= x){
                ++ans;
            }
        }
        return (ans - n);
    }
};
int main(){
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    int q;
    cin >> q;
    vector<vector<pair<int, int>>> queries(n + 1);
    for(int i = 0; i < q; ++i){
        int l, r;
        cin >> l >> r;
        queries[r].push_back({l, i});
    }

    vector<int> res(q);

    SegmentTree s(n + 1);
    for(int i = 1; i <= n; ++i){
        // set the last occurence of a[i] to i
        s.set(a[i], i);

        for(auto [l, ind] : queries[i]){
            // find the smallest x, such that last occurence of x < l
            res[ind] = s.get(l);
        }
    }
    for(int elem : res){
        cout << elem << '\n';
    }
    cout << '\n';

    return 0;
}

Tags mex, range query

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en19 English one_autum_leaf 2023-06-27 20:24:52 15 Tiny change: 'discussed [here](ht' -> 'discussed in the comment [here](ht'
en18 English one_autum_leaf 2023-06-27 20:24:09 30 (published)
en17 English one_autum_leaf 2023-06-27 20:22:14 26 Tiny change: ', 0]$.\n\n![ ](' -> ', 0]$.\n\nWe start at root node.\n\n![ ]('
en16 English one_autum_leaf 2023-06-27 20:21:28 41
en15 English one_autum_leaf 2023-06-27 20:19:03 2 Tiny change: 'dash; $O(nlog n + q(log ' -> 'dash; $O(n \log_n + q(log '
en14 English one_autum_leaf 2023-06-27 20:16:20 1 Tiny change: 'O(q log n). Updating' -> 'O(q log n)$. Updating'
en13 English one_autum_leaf 2023-06-27 20:15:42 253
en12 English one_autum_leaf 2023-06-27 20:12:53 15 Tiny change: 'array is $1, 0$.\n\n![ ]' -> 'array is $[a_2, a_3] = [1, 0]$.\n\n![ ]'
en11 English one_autum_leaf 2023-06-27 20:12:17 519 Tiny change: 'imgur.com/a/UkzuMa5)\n\n~~~~~' -> 'imgur.com/5TOuXF6)\n\n~~~~~'
en10 English one_autum_leaf 2023-06-27 20:02:50 35 Tiny change: '., a_r$.\n\n~~~~~\' -> '., a_r$.\n![ ](https://imgur.com/a/UkzuMa5)\n\n~~~~~\'
en9 English one_autum_leaf 2023-06-27 19:48:07 163
en8 English one_autum_leaf 2023-06-27 19:45:55 1610 Tiny change: 'egin{math}a_x = 1\end{math}\begin{math}a_x = 1\end{math}\begin{math}' -> 'egin{math}'
en7 English one_autum_leaf 2023-06-27 19:10:31 36
en6 English one_autum_leaf 2023-06-27 19:09:34 3 Tiny change: 'et $b_x = $ \bigl\{\n\n~~~~~\' -> 'et $b_x = \bigl\{ $\n\n~~~~~\'
en5 English one_autum_leaf 2023-06-27 19:09:15 199
en4 English one_autum_leaf 2023-06-27 19:00:34 1566
en3 English one_autum_leaf 2023-06-27 18:52:21 180
en2 English one_autum_leaf 2023-06-27 18:50:49 2 Tiny change: 'y $a_l, a_l+1, ..., a_r' -> 'y $a_l, a_{l+1}, ..., a_r'
en1 English one_autum_leaf 2023-06-27 18:50:11 222 Initial revision (saved to drafts)