Requêtes de Permutation de Beauté#11732
Le problème utilise l'indexation à partir de , c'est-à-dire que les tableaux sont numérotés à partir de .
Une permutation de longueur est un tableau d'entiers positifs où chaque élément apparaît exactement une fois et chaque nombre de à n - 1 est présent. Par exemple, , [0, 2, 1], [0, 3, 1, 2] sont des permutations, tandis que [0, 1, 3], , [0, 1, 0] ne le sont pas.
Nous définissons l'ensemble des transformations atteignables de la permutation par rapport à l'ensemble comme l'ensemble des permutations qui peuvent être obtenues à partir de en appliquant l'opération suivante un nombre quelconque de fois (possiblement ) :
Choisissez deux indices (0 \leq i, j \leq n - 1) tels que i \oplus j \in S, et échangez les éléments de la permutation aux positions et .
Ici, désigne l'opération XOR bit à bit.
L'ensemble est appelé bon par rapport à la permutation si l'ensemble des transformations atteignables de la permutation contient une permutation d'identité.
Nous appelons une permutation de longueur permutation d'identité si ce qui suit est vrai : a_i = i (0 \leq i \leq m - 1).
La beauté de la permutation est définie comme la taille minimale d'un bon ensemble par rapport à elle.
Vous recevez une permutation de longueur . Vous devez afficher la beauté initiale de la permutation. Vous recevez également requêtes. Chaque requête consiste en deux nombres . Après chaque requête, vous devez échanger les éléments aux positions et . Notez que la permutation conserve les changements après chaque requête. En réponse à chaque requête, vous devez afficher la beauté de la permutation résultante.
La première ligne contient deux nombres (1 \leq n \leq 5 \cdot 10^5) et (0 \leq \beta \leq 1).
La deuxième ligne contient nombres p_i (0 \leq p_i < n) — la permutation de départ.
La troisième ligne contient un nombre (0 \leq q \leq 5 \cdot 10^5) — le nombre de requêtes.
Dans les lignes suivantes, deux nombres a_i', b_i' (0 \leq a_i', b_i' \leq n - 1) sont donnés — les paramètres de la -ème requête.
Les valeurs de la -ème requête sont déterminées comme suit. Soit la réponse à la requête précédente, ou la beauté de la permutation initiale si c'est la première requête. Alors a_i = (a_i' + last \cdot \beta) \bmod n, et b_i = (b_i' + last \cdot \beta) \bmod n.
Dans la première ligne, affichez la beauté de la permutation initiale.
Dans les lignes suivantes, affichez les réponses aux requêtes.
Exemple
Après la deuxième requête, la permutation devient [5, 2, 1, 3, 4, 0, 6].
Soit S = \{3, 6\}. En utilisant cet ensemble, nous pouvons effectuer les échanges suivants pour transformer la permutation en la permutation d'identité :
Échanger i = 0 et j = 3. La permutation devient [\textbf{3}, 2, 1, \textbf{5}, 4, 0, 6].
Échanger i = 3 et j = 5. La permutation devient [3, 2, 1, \textbf{0}, 4, \textbf{5}, 6].
Échanger i = 1 et j = 2. La permutation devient [3, \textbf{1}, \textbf{2}, 0, 4, 5, 6].
Échanger i = 0 et j = 3. La permutation devient [\textbf{0}, 1, 2, \textbf{3}, 4, 5, 6].
Il peut être prouvé qu'il est impossible d'obtenir la permutation d'identité en effectuant des opérations avec |S| \leq 1.
( points) : n \leq 8, \beta = 0;
( points) : n \leq 32, q = 0, \beta = 0;
( points) : il est garanti que la réponse ne dépasse pas , \beta = 0;
( points) : n \cdot q \leq 9 \cdot 10^6, \beta = 0;
( points) : q \leq 10^4;
( points) : \beta = 0;
( points) : aucune restriction supplémentaire.