Consultas de GCD en rango
Se te proporciona un array de
n elementos y q consultas. Existen dos tipos de consultas: calcular el greatest common divisor (GCD) para un rango específico y actualizar un elemento en una posición determinada. Tu objetivo es procesar estas consultas de manera eficiente.Entrada
La primera línea de la entrada contiene dos enteros
n y q (1 ≤ n, q ≤ 100 000), que representan la cantidad de elementos en el array y el número de consultas, respectivamente.La segunda línea incluye
n enteros separados por espacios (), que son los elementos iniciales del array.Las siguientes
q líneas describen cada consulta:- For range GCD queries: The line starts with the number 1 followed by two integers and (), representing the range of indices
[]for which the GCD needs to be calculated.
- For array update queries: The line starts with the number 2 followed by two integers and (), representing the index of the element to be updated and its new value .
Salida
Por cada consulta de GCD en rango, imprime en una línea separada el GCD de los elementos dentro del rango solicitado.
Ejemplos
Entrada | Salida |
6 4
12 8 16 24 36 48
1 2 5
2 4 10
1 1 6
1 3 6 | 4
2
2 |
Constraints
Time limit: 0.8 seconds
Memory limit: 512 MB
Output limit: 1 MB