Starting with array of N positive integers, support Q queries. Each query contains a positive integer i. To answer the query, replace each element of the array with the result of xoring it with i, then output the earliest index of the smallest element in the array. Each query changes the array.

I could only come up with O(N*Q). I try to think of range update data structure but xor can make number bigger so I don’t think it’s right way.

How to solve faster?

#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;
}

Example input

5
1 2 3 4 5
3
1
2
6

Example output

0
2
4

Example output explanation

First query is 1. After xor array with 1, it becomes 0 3 2 5 4. Smallest number: index 0

Second query is 2. After xor previous array with 2, it becomes 2 1 0 7 6. Smallest number: index 2

Second query is 6. After xor previous array with 6, it becomes 4 7 6 1 0. Smallest number: index 4