Consultas de permutaciones de belleza#11732
El problema utiliza indexación , es decir, los arreglos están numerados desde .
Una permutación de longitud es un arreglo de números enteros positivos, donde cada elemento aparece exactamente una vez y cada número desde hasta n - 1 está presente. Por ejemplo, , [0, 2, 1], [0, 3, 1, 2] son permutaciones, mientras que [0, 1, 3], , [0, 1, 0] no son permutaciones.
Definimos el conjunto de transformaciones alcanzables de la permutación en relación con el conjunto como el conjunto de permutaciones que se pueden obtener de aplicando la siguiente operación cualquier número de veces (posiblemente ):
Elija dos índices (0 \le i, j \le n - 1), de modo que i \oplus j \in S, y cambie los elementos de la permutación en las posiciones y .
Aquí, denota la operación XOR a nivel de bits.
El conjunto se considera bueno en relación con la permutación si el conjunto de transformaciones alcanzables de la permutación contiene una permutación identidad.
Llamamos a una permutación de longitud una permutación identidad si se cumple lo siguiente: a_i = i (0 \le i \le m - 1).
La belleza de la permutación se define como el tamaño mínimo de un conjunto bueno en relación con ella.
Se le da una permutación de longitud . Debe imprimir la belleza inicial de la permutación. Además, recibe consultas. Cada consulta consiste en dos números . Después de cada consulta, debe intercambiar los elementos en las posiciones y . Tenga en cuenta que la permutación mantiene los cambios después de cada consulta. Como respuesta a cada consulta, debe imprimir la belleza de la permutación resultante.
La primera línea contiene dos números (1 \le n \le 5 \cdot 10^5) y (0 \le \beta \le 1).
La segunda línea contiene números p_i (0 \le p_i < n) — la permutación inicial.
La tercera línea contiene un número (0 \le q \le 5 \cdot 10^5) — el número de consultas.
En las siguientes líneas se dan dos números a_i', b_i' (0 \le a_i', b_i' \le n - 1) — los parámetros de la -ésima consulta.
Los valores de la -ésima consulta se determinan de la siguiente manera. Sea la respuesta a la consulta anterior o la belleza de la permutación original si es la primera consulta. Entonces,
En la primera línea, imprima la belleza de la permutación original.
En las siguientes líneas, imprima las respuestas a las consultas.
Ejemplo
Después de la segunda consulta, la permutación se convierte en [5, 2, 1, 3, 4, 0, 6].
Sea S = \{3, 6\}. Con este conjunto, podemos realizar las siguientes operaciones de intercambio para transformar la permutación en la permutación identidad:
Intercambiar i = 0 y j = 3. La permutación se convierte en [\textbf{3}, 2, 1, \textbf{5}, 4, 0, 6].
Intercambiar i = 3 y j = 5. La permutación se convierte en [3, 2, 1, \textbf{0}, 4, \textbf{5}, 6].
Intercambiar i = 1 y j = 2. La permutación se convierte en [3, \textbf{1}, \textbf{2}, 0, 4, 5, 6].
Intercambiar i = 0 y j = 3. La permutación se convierte en [\textbf{0}, 1, 2, \textbf{3}, 4, 5, 6].
Se puede demostrar que es imposible obtener la permutación identidad mediante operaciones con |S| \le 1.
( puntos): n \le 8, \beta = 0;
( puntos): n \le 32, q = 0, \beta = 0;
( puntos): se garantiza que la respuesta no exceda , \beta = 0;
( puntos): n \cdot q \le 9 \cdot 10^6, \beta = 0;
( puntos): q \le 10^4;
( puntos): \beta = 0;
( puntos): sin restricciones adicionales.