Algoritmos e Estruturas de Dados

Prefix Sum Query (Consulta de Soma Prefixada)

É-lhe dado um array de n inteiros positivos. O seu objetivo é processar q consultas, em que cada consulta pode ser de dois tipos:
  1. Verificar se existe um subarray prefixo no array com soma igual a um valor s.
  1. Atualizar o valor em um índice específico do array.
Implemente um programa para responder a essas consultas de forma eficiente.

Entrada

A primeira linha contém dois inteiros n e q (1 ≤ n, q ≤ 100 000), separados por um espaço, que representam o tamanho do array e o número de consultas, respetivamente.
A segunda linha contém n inteiros positivos, que são os elementos do array. Cada elemento é positivo e não excede .
As q linhas seguintes descrevem as consultas. Cada consulta é especificada por um tipo de consulta (1 ou 2), seguido dos parâmetros necessários:
  • Para consultas do tipo 1: um inteiro s.
  • Para consultas do tipo 2: uma posição p e um valor x a atualizar nesse índice.

Saída

Para cada consulta do tipo 1, imprima YES se existir um subarray prefixo com soma igual a s, caso contrário imprima NO.

Exemplos

Entrada
Saída
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

To check your solution you need to sign in
Sign in to continue