异或后的最小元素

Question

从N个正整数数组开始，支持Q个查询。每个查询包含一个正整数 i。为了回答查询，将数组中的每个元素替换为与 i 进行异或的结果，然后输出数组中最小元素的最早索引。每个查询都会更改数组。

我只能想出O(N*Q)。我尝试考虑范围更新数据结构，但异或可以使数字更大，所以我认为这不是正确的方法。

如何更快解决？

#include <bits/stdc++.h>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    int Q;
    cin >> Q;
    for (int j = 0; j < Q; j++) {
        int i;
        cin >> i;
        for (int k = 0; k < N; k++) {
            A[k] = A[k] ^ i;
        }
        int mini = 0;
        for (int k = 0; k < N; k++) {
            if (A[k] < A[mini]) {
                mini = k;
            }
        }
        cout << mini << '\n';
    }
    return 0;
}

输入示例

5
1 2 3 4 5
3
1
2
6

输出示例

0
2
4

示例输出说明

第一个查询是1。数组与1异或后，变成0 3 2 5 4。最小的数字：索引0

第二个查询是 2。与 2 异或前一个数组后，它变成 2 1 0 7 6。最小的数字：索引 2

第二个查询是 6。将前一个数组与 6 进行异或后，变为 4 7 6 1 0。最小数字：索引 4

Answer 1

您可以使用线段树，这是查询数组的常用技术，并将时间复杂度降低到 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