Consultas de suma de prefijos
Se te proporciona un arreglo de
n números enteros positivos. Tu tarea es procesar q consultas, donde cada una puede ser de dos tipos:- Verificar si existe un subarreglo prefijo del arreglo cuyo valor total sea igual a un número
s.
- Actualizar el valor en un índice específico del arreglo.
Escribe un programa que responda a estas consultas de manera eficiente.
Entrada
La primera línea contiene dos enteros
n y q (1 ≤ n, q ≤ 100 000), separados por un espacio, que representan el tamaño del arreglo y la cantidad de consultas, respectivamente.La segunda línea contiene
n números enteros positivos, los cuales forman el arreglo; cada uno de ellos es positivo y no excede .A continuación, se proporcionan
q líneas, cada una describiendo una consulta. Cada consulta se indica con un tipo (1 o 2) junto con los parámetros requeridos:- Para una consulta de tipo 1: un entero
s.
- Para una consulta de tipo 2: una posición
py un valorxque se asignará en ese índice.
Salida
Por cada consulta de tipo 1, imprime
YES si existe un subarreglo prefijo cuya suma sea igual a s; en caso contrario, imprime NO.Ejemplos
Entrada | Salida |
5 3
1 2 3 4 5
1 10
2 2 3
1 15 | YES
NO |
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB