Zamjene.

View as PDF

Submit solution


Points: 100 (partial)
Time limit: 3.0s
Memory limit: 256M

Author:
Problem types
Allowed languages
C, C++, Java, Python

Dominik ha imaginado una serie de números enteros positivos \(p_1, ..., p_n\). Denotemos la versión ordenada de ese arreglo como \(q_1, ..., q_n\).

Además, imaginó un conjunto de sustituciones permitidas. Si un par \((X, Y)\) es un miembro del conjunto sustituciones permitidas, Dominik puede intercambiar los números en las posiciones de \(X\) y \(Y\) en el arreglo \(p\).

Marin le está dando a Dominik Q consultas, y cada una de ellas es de uno de los siguientes tipos:

1- Intercambiar números en posiciones \(A\) y \(B\).

2- Agregar el par \((A, B)\) al conjunto de sustituciones permitidas. Marin puede dar un par que ya esté en el conjunto

3- ¿Diga si es posible ordenar la matriz usando solo las sustituciones permitidas? Las sustituciones se pueden utilizar en un orden arbitrario, y cada sustitución se puede realizado un número arbitrario de veces.

4- Llamemos a un par de posiciones \((A, B)\) vinculadas si el número de la posición \(A\) es posible transferir a la posición \(B\) utilizando solo las subtitulaciones permitidas. Llamemos al conjunto de todas las posiciones vinculadas para colocar \(A\) la nube de \(A\). Una nube es buena si es posible para cada posición \(j\) de la nube lograr que \(p_j = q_j\) utilizando una serie de sustituciones permitidas.

Debes responder cuántos pares diferentes las posiciones \((A, B)\) existen de tal manera que contiene:

  • Las posiciones \(A\) y \(B\) no están vinculadas una.

  • La nube de \(A\) no es buena y la nube de \(B\) no es buena

  • Si agregamos el par \((A, B)\) al conjunto de sustituciones permitidas, la nube de \(A\) (uniéndola con la de \(B\)) se vuelve buena.

Tenga en cuenta: Los pares \((A, B)\) y \((B, A)\) se consideran un par idéntico.

Entrada

La primera línea de entrada contiene dos enteros \(N\) y \(Q (1 ≤ N, Q ≤ 100 000)\).

La segunda línea de entrada contiene \(N\) enteros \(p_1, ..., p_n\) \((1 ≤ p_1, ..., p_n ≤ 100 000)\).

Cada una de las siguientes líneas \(Q\) contiene una consulta en el siguiente formato:

  • El primer número de la línea es el tipo de consulta \(T\) del conjunto \({1, 2, 3, 4}\).

  • \(A\) y \(B\) siguen \((1 ≤ A, B ≤ N)\), si el tipo de consulta \(T\) es \(1\) o \(2\), dos números enteros diferentes Representan la sustitución \((A, B)\).

Salida

Para cada consulta de tipo \(3\) o \(4\), envíe la respuesta en su línea separada. La respuesta a la consulta de tipo \(3\) es \("DA"\) (sí) o \("NE"\) (no), sin las comillas, y la respuesta a la consulta de tipo \(4\) es un número entero no negativo de la tarea.

Puntuación

En casos de prueba que valen \(50\%\) del total de puntos, tendrá \(N, Q ≤ 1000\).

Ejemplos

Ejemplo de entrada 1
3 5
1 3 2
4
3
2 2 3
4
3
Ejemplo de salida 1
1
NE
0
DA
Ejemplo de entrada 2
5 5
4 2 1 4 4
3
4
1 1 3
3
4
Ejemplo de salida 2
NE
1
DA
0
Ejemplo de entrada 3
4 10
2 1 4 3
3
4
1 1 2
3
4
2 2 3
2 1 2
4
2 3 4
3
Ejemplo de salida 3
NE
2
NE
1
3
DA
Aclaración del primer caso de prueba:

La respuesta a la primera consulta es \(1\) porque el par de posiciones \((2, 3)\) cumple con todos los requisitos dados. La respuesta a la segunda pregunta es \(NE\) (no) porque es imposible transferir los números \(2\) y \(3\) a las posiciones correspondientes, porque el conjunto de sustituciones permitidas está vacío.

Después de la tercera consulta, agregamos el par \((2, 3)\) al conjunto de sustituciones permitidas. La respuesta a la cuarta consulta ahora es \(0\) porque \(2\) y \(3\) ya están vinculados, y la respuesta a la quinta La consulta es \(DA\) (sí), porque es posible ordenar el arreglo aplicando la sustitución permitida \((2, 3)\).


Comments

There are no comments at the moment.