Наименьший элемент после xor

Вы можете использовать дерево сегментов, которое является распространенным методом запроса массивов и снижает временную сложность до O(N log N):

Ссылка

Код

#include <iostream>
#include <vector>

struct SegmentTree
{
    int N;
    std::vector<int> A;
    std::vector<int> seg;
    std::vector<std::pair<int, int>> tree;

    void build_tree(
        const int node,
        const int left,
        const int right)
    {
        if (left == right)
        {
            tree[node] = {A[left], left};
        }
        else
        {
            int mid = left + (right - left) / 2;
            build_tree(2 * node + 1, left, mid);
            build_tree(2 * node + 2, mid + 1, right);
            tree[node] = std::min(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }

    void update_xor(
        const int node,
        const int left,
        const int right)
    {
        if (seg[node] != 0)
        {
            tree[node].first ^= seg[node];
            if (left != right)
            {
                seg[2 * node + 1] ^= seg[node];
                seg[2 * node + 2] ^= seg[node];
            }
            seg[node] = 0;
        }
    }

    void update_tree(
        const int l,
        const int r,
        const int val,
        const int node,
        const int left,
        const int right)
    {
        update_xor(node, left, right);
        if (left > right || left > r || right < l)
            return;
        if (left >= l && right <= r)
        {
            seg[node] ^= val;
            update_xor(node, left, right);
            return;
        }
        const int mid = left + (right - left) / 2;
        update_tree(l, r, val, 2 * node + 1, left, mid);
        update_tree(l, r, val, 2 * node + 2, mid + 1, right);
        tree[node] = std::min(tree[2 * node + 1], tree[2 * node + 2]);
    }

    std::pair<int, int> get_min(
        const int l,
        const int r,
        const int node,
        const int left,
        const int right)
    {
        update_xor(node, left, right);
        if (left > right || left > r || right < l)
            return {INT_MAX, -1};
        if (left >= l && right <= r)
            return tree[node];
        const int mid = left + (right - left) / 2;
        return std::min(
            get_min(l, r, 2 * node + 1, left, mid),
            get_min(l, r, 2 * node + 2, mid + 1, right));
    }

    SegmentTree(const std::vector<int> &nums) : A(nums)
    {
        N = std::size(A);
        tree.resize(4 * N);
        seg.resize(4 * N, 0);
        build_tree(0, 0, N - 1);
    }

    void update(const int l, const int r, const int val)
    {
        update_tree(l, r, val, 0, 0, N - 1);
    }

    std::pair<int, int> query(const int l, const int r)
    {
        return get_min(l, r, 0, 0, N - 1);
    }
};

int main()
{
    std::vector<int> A = {1, 2, 3, 4, 5};
    std::vector<int> Q = {1, 2, 6};
    for (auto &q : Q)
    {
        for (int i = 0; i < std::size(A); ++i)
            A[i] ^= q;
        SegmentTree seg_tree(A);
        std::pair<int, int> res = seg_tree.query(0, std::size(A) - 1);
        std::cout << res.second << "\n";
    }

    return 0;
}

Принты

0
2
4

Представляйте элементы массива как двоичные числа фиксированной ширины (т. е. последовательности битов 0 и 1), начиная со старшего бита. Создайте из них двоичное дерево, сохранив индекс массива в дереве внизу.

Если фиксированная ширина равна W, на любой отдельный запрос можно ответить за время O(W); при спуске по дереву, если есть одна ветвь, следуйте за ней, в противном случае перейдите по ветке «0», если значение xor имеет бит «0» в этой позиции, в противном случае перейдите к ветке «1».

Интуиция здесь проста; если в массиве есть хотя бы один элемент, имеющий тот же самый старший бит, что и значение xor, наименьший элемент в массиве должен быть одним из этих элементов. И так далее до следующего значимого бита. Trie делает поиск этих наборов эффективным.

Чтобы выполнить последовательные запросы, вместо обновления структуры данных выполните запрос к выполняющемуся XOR запросов на данный момент. Итак, если запросы Q1, Q2, Q3, Q4..., то вместо этого запросите Q1, Q1^Q2, Q1^Q2^Q3, Q1^Q2^Q3^Q4,... (где ^ — XOR). Это означает, что вам вообще не нужно обновлять дерево.