Beauty Permutation Queries (Editorial)

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 min_S of the good set $S$ in this case:

1. min_S=0 \leftrightarrow p_i=i for all 0 \le i < n;

2. min_S=1 \leftrightarrow \exists i: i \neq p_i and \exists x: \forall i (i = p_i \lor i \oplus p_i = x);

3. Otherwise min_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 \ldots \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 log n) and output it. The complexity of the solution is O(q \cdot n \cdot log n).

Group 5. Using a segment tree, we can maintain the XOR basis of the array in O(log^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(log^2(n)). Thus, the update operation will work in O(log^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.