Redaksiya

Group 1. Enumerate all possible sets $S$ and check if we can sort the permutation for each of the sets.

Group 2. The size of the minimum set when $n\le 32$ does not exceed $5$ (if we choose $S=\{1,2,4,8,16\}$, it is not difficult to sort any permutation of size up to $32$), so we can only enumerate sets of size up to $4$ and check if we can sort the permutation.

Group 3. There are three possible cases depending on the minimum size $mi{n}_S$ of the good set $S$ in this case:

1. $mi{n}_S=0\leftrightarrow p_i=i$ for all $0\le i<n$;

2. $mi{n}_S=1\leftrightarrow \exists i:i\ne p_i$ and $\exists x:\forall i(i=p_i\vee i\oplus p_i=x)$;

3. Otherwise $mi{n}_S=2$.

Using std::map, we can maintain a set of all values $i\oplus p_i$ and check how many unique non-zero values $i\oplus p_i$ exist.

Group 4. Let us have some set $S$, with which we can sort our permutation using the operations from the condition.

Consider the element that was at position $i$ in the initial permutation. Obviously, in the identity permutation, it is at position $p_i$. Let's consider the sequence of positions that the element of the permutation with value $p_i$ visited before moving to its final position:

where $c_{i+1}=c_i\oplus x_i$, with $x_i\in S$ for such $i$ that $0\le i<k$.

Let's express $c_k$ in terms of $c_0$: $c_k=c_0\oplus x_0\oplus x_1\oplus \dots \oplus x_{k-1}$. Then we have that

That is, in order to move the element with value $p_i$ to its position, it is necessary that the XORs of the elements of the set $S$ can represent the number $i\oplus p_i$ for each $i$: $0\le i<n$.

Recall the XOR basis. The XOR basis is the minimal set of numbers that can represent any number of a given set using XOR combinations. You can learn more here.

It can be proven that if we take $S$ as the XOR basis of the numbers $i\oplus p_i$ constructed by the algorithm given below, then this will be one of the minimum size sets with which we can sort the given permutation.

vector <int> basis;

void add (int x) {
    for (int i : basis) {
        x = min(x, x ^ i);
    }
    if (x) {
        for (int &i : basis) {
            i = min(i, i ^ x);
        }
        basis.push_back(x);
    }
}

Then the answer to each query is the size of the XOR basis built on the numbers $i\oplus p_i$.

Thus, after each query, we can compute the size of the XOR basis in $O(n\cdot logn)$ and output it. The complexity of the solution is $O(q\cdot n\cdot logn)$.

Group 5. Using a segment tree, we can maintain the XOR basis of the array in $O(lo{g}^3(n))$ per query. In each vertex, we will store the XOR basis of the numbers $i\oplus p_i$ for which the corresponding segment of the segment tree is responsible.

Merging two bases can be done in place in $O(lo{g}^2(n))$. Thus, the update operation will work in $O(lo{g}^3(n))$.

Group 6. When $\beta =0$, we know all queries in advance. We can add elements to the XOR basis. However, unfortunately, we cannot remove them. Given all this, we can use this technique, which allows us to delete from a structure where we can add if the queries are given in advance.

Group 7.

How to maintain the XOR basis online in $O({\log }^{2}n)$ per query can be learned from this link.