La estructura de datos de un array persistente permite mantener múltiples versiones de un arreglo a lo largo del tiempo. Cada operación de modificación o consulta sobre una versión específica genera una nueva versión, dejando las versiones anteriores inalteradas. Esto es fundamental para problemas que requieren acceso a estados pasados de los datos sin afectar la integridad de las versiones ya existentes.

Descripción del Problema

Se requiere mantener un array de longitud \(N\) y soportar las siguientes operaciones:

1. Modificar el valor en una posición específica de una versión histórica.
2. Acceder al valor en una posición específica de una versión histórica.

Cada operación, ya sea de modificación o de consulta, resulta en la creación de una nueva versión del array. Las versiones se numeran consecutivamente a partir de 1, siendo la versión 0 el estado inicial del array.

Formato de Entrada

La primera línea contiene dos enteros positivos \(N\) y \(M\), que representan la longitud del array y el número total de operaciones a realizar, respectivamente.

La segunda línea contiene \(N\) enteros, que son los valores iniciales del array (\\(a\_i\\), para \\(1 \leq i \leq N\\)).

Las siguientes \(M\) líneas describen las operaciones. Cada línea comienza con un entero \(v_i\), que indica la versión base sobre la cual se realizará la operación:

• **Operación 1 (Modificación):** v_i 1 loc_i value_i. Esto significa que, basándose en la versión \\(v\_i\\), el valor en la posición \\({loc}\_i\\) se actualizará a \\({value}\_i\\).
• **Operación 2 (Consulta):** v_i 2 loc_i. Esta operación consulta el valor en la posición \\({loc}\_i\\) de la versión \\(v\_i\\).

Formato de Salida

Por cada operación de tipo 2 (consulta), se debe imprimir el valor obtenido en una nueva línea.

Ejemplo de Entrada

5 10
59 46 14 87 41
0 2 1
0 1 1 14
0 1 1 57
0 1 1 88
4 2 4
0 2 5
0 2 4
4 2 1
2 2 2
1 1 5 91

Ejemplo de Salida

59
87
41
87
88
46

Restricciones

• Para el 100% de los datos: \\(1 \leq N, M \leq {10}^6\\)
• \\(1 \leq {loc}\_i \leq N\\)
• \\(0 \leq v\_i < i\\)
• \\(-{10}^9 \leq a\_i, {value}\_i \leq {10}^9\\)

Solución con Árbol de Segmentos Persistente

La implementación eficiente de un array persistente se logra mediante el uso de un Árbol de Segmentos persistente. La característica principal de esta estructura es su capacidad para compartir la mayor parte de su estructura entre diferentes versiones del array. En lugar de copiar todo el árbol para cada nueva versión, solo se recrean los nodos que están directamente afectados por una operación.

Cuando se realiza una operación de actualización en una posición específica, se generan nuevos nodos a lo largo de la ruta desde la raíz del árbol hasta el nodo hoja que corresponde a la posición modificada. Los nodos que no están en esta ruta de modificación se reutilizan de la versión atnerior, lo que significa que sus punteros permanecen inalterados. Este enfoque asegura que cada actualización solo añade un número logarítmico (\\(O(\log N)\\)) de nuevos nodos al árbol. Esta optimización es crucial para mantener tanto el uso de memoria como el tiempo de ejecución dentro de límites aceptables para un gran número de operaciones.

Las consultas se manejan de forma similar a un árbol de segmentos convencional, pero siempre comenzando desde la raíz de la versión específica que se desea consultar. Para cada operación de tipo 2 (consulta), el problema especifica que se debe generar una nueva versión, que será una copia idéntica de la versión consultada.

#include <iostream>
#include <vector>
#include <cstdio> // Para usar scanf/printf, que suelen ser más eficientes en programación competitiva

// Definición de las constantes máximas para N y M
const int MAX_N_M = 1000005;

// Para N=10^6 y M=10^6:
// Un árbol de segmentos inicial requiere aproximadamente 2*N nodos.
// Cada operación de actualización añade alrededor de log2(N) nuevos nodos.
// Considerando que log2(10^6) es aproximadamente 20,
// el número total de nodos se estima en: (2*N) + (M * log2(N))
// Esto es, 2 * 10^6 + 10^6 * 20 = 22 * 10^6 nodos.
// Se usa un factor de seguridad para el tamaño del arreglo de nodos.
const int MAX_TOTAL_NODES = MAX_N_M * 25; // Aproximadamente 25 millones de nodos

// Estructura que define un nodo del árbol de segmentos
struct Node {
   long long value;       // El valor almacenado en un nodo hoja (puede ser de -10^9 a 10^9)
   int left_child_idx;    // Índice del nodo hijo izquierdo
   int right_child_idx;   // Índice del nodo hijo derecho
};

// Arreglo global para almacenar todos los nodos del árbol de segmentos
Node segment_tree_nodes[MAX_TOTAL_NODES];
// Contador para asignar un índice único a cada nuevo nodo
int next_available_node_idx = 0;

// Arreglo que almacena los índices de la raíz para cada versión del array.
// root_pointers[0] es la raíz de la versión inicial (versión 0).
// root_pointers[i] es la raíz de la versión generada después de la operación 'i'.
int root_pointers[MAX_N_M];

// Arreglo para guardar los valores iniciales del array
long long initial_array_values[MAX_N_M];

/**
* @brief Construye el árbol de segmentos inicial para la versión 0.
* @param current_l El límite inferior del rango actual del nodo.
* @param current_r El límite superior del rango actual del nodo.
* @return El índice de la raíz del árbol o subárbol construido.
*/
int build_initial_tree(int current_l, int current_r) {
   int current_node_idx = ++next_available_node_idx; // Asigna un nuevo índice de nodo

   if (current_l == current_r) { // Caso base: es un nodo hoja
       segment_tree_nodes[current_node_idx].value = initial_array_values[current_l];
       segment_tree_nodes[current_node_idx].left_child_idx = 0; // Los nodos hoja no tienen hijos
       segment_tree_nodes[current_node_idx].right_child_idx = 0;
       return current_node_idx;
   }

   int mid = current_l + (current_r - current_l) / 2;
   // Recursivamente construye los hijos izquierdo y derecho
   segment_tree_nodes[current_node_idx].left_child_idx = build_initial_tree(current_l, mid);
   segment_tree_nodes[current_node_idx].right_child_idx = build_initial_tree(mid + 1, current_r);
   // Para este problema, los nodos internos no necesitan almacenar un valor agregado
   segment_tree_nodes[current_node_idx].value = 0; 

   return current_node_idx;
}

/**
* @brief Actualiza un valor en una versión específica del array, creando una nueva versión.
* @param previous_root_idx El índice de la raíz del subárbol de la versión anterior.
* @param target_pos La posición en el array que se desea actualizar.
* @param new_value El nuevo valor para la posición target_pos.
* @param current_l El límite inferior del rango actual del nodo.
* @param current_r El límite superior del rango actual del nodo.
* @return El índice de la raíz del nuevo subárbol con la modificación.
*/
int update_value_in_version(int previous_root_idx, int target_pos, long long new_value, int current_l, int current_r) {
   int new_node_idx = ++next_available_node_idx; // Asigna un nuevo índice para el nodo
   // Copia todos los datos del nodo de la versión anterior al nuevo nodo.
   // Esto es clave para la persistencia: los hijos no afectados por la actualización
   // seguirán apuntando a los mismos nodos de la versión anterior.
   segment_tree_nodes[new_node_idx] = segment_tree_nodes[previous_root_idx]; 

   if (current_l == current_r) { // Se encontró el nodo hoja correspondiente a target_pos
       segment_tree_nodes[new_node_idx].value = new_value;
       return new_node_idx;
   }

   int mid = current_l + (current_r - current_l) / 2;
   if (target_pos <= mid) { // La actualización se encuentra en el rango del hijo izquierdo
       segment_tree_nodes[new_node_idx].left_child_idx =
           update_value_in_version(segment_tree_nodes[previous_root_idx].left_child_idx, target_pos, new_value, current_l, mid);
   } else { // La actualización se encuentra en el rango del hijo derecho
       segment_tree_nodes[new_node_idx].right_child_idx =
           update_value_in_version(segment_tree_nodes[previous_root_idx].right_child_idx, target_pos, new_value, mid + 1, current_r);
   }

   return new_node_idx;
}

/**
* @brief Consulta el valor en una posición específica de una versión del array.
* @param root_idx El índice de la raíz de la versión del árbol a consultar.
* @param target_pos La posición en el array que se desea consultar.
* @param current_l El límite inferior del rango actual del nodo.
* @param current_r El límite superior del rango actual del nodo.
* @return El valor en la posición target_pos de la versión especificada.
*/
long long query_value_from_version(int root_idx, int target_pos, int current_l, int current_r) {
   if (current_l == current_r) { // Se encontró el nodo hoja
       return segment_tree_nodes[root_idx].value;
   }

   int mid = current_l + (current_r - current_l) / 2;
   if (target_pos <= mid) { // La posición a consultar está en el rango del hijo izquierdo
       return query_value_from_version(segment_tree_nodes[root_idx].left_child_idx, target_pos, current_l, mid);
   } else { // La posición a consultar está en el rango del hijo derecho
       return query_value_from_version(segment_tree_nodes[root_idx].right_child_idx, target_pos, mid + 1, current_r);
   }
}

int main() {
   // Deshabilita la sincronización de C++ iostreams con C stdio.
   // Aunque se usa scanf/printf aquí, es una buena práctica para optimizar I/O.
   std::ios_base::sync_with_stdio(false); 

   int N, M;
   scanf("%d %d", &N, &M);

   // Lee los valores iniciales para el array. Se indexa desde 1.
   for (int i = 1; i <= N; ++i) {
       scanf("%lld", &initial_array_values[i]);
   }

   // Construye el árbol de segmentos inicial para la versión 0.
   root_pointers[0] = build_initial_tree(1, N);

   // Procesa las M operaciones
   for (int i = 1; i <= M; ++i) {
       int v_base, op_type, target_pos;
       scanf("%d %d %d", &v_base, &op_type, &target_pos);

       if (op_type == 1) { // Operación de modificación
           long long new_val;
           scanf("%lld", &new_val);
           // La versión actual (i) se genera a partir de la versión base (v_base)
           // con el valor en target_pos actualizado a new_val.
           root_pointers[i] = update_value_in_version(root_pointers[v_base], target_pos, new_val, 1, N);
       } else { // Operación de consulta
           // Una consulta también genera una nueva versión, que es una copia idéntica
           // de la versión base sobre la que se consulta.
           root_pointers[i] = root_pointers[v_base]; 
           long long result = query_value_from_version(root_pointers[v_base], target_pos, 1, N);
           printf("%lld\n", result); // Imprime el resultado de la consulta
       }
   }

   return 0;
}