Query sulle somme prefisse
Vi viene fornito un array di
n interi positivi. Il vostro compito consiste nel gestire q query, ognuna delle quali può essere di due tipi:- Verificare se esiste un sottoarray prefisso dell’array con una somma uguale a un dato valore
s.
- Aggiornare il valore in una posizione specifica dell’array.
Scrivete un programma che risponda a queste query in modo efficiente.
Input
La prima riga contiene due interi
n e q (1 ≤ n, q ≤ 100 000), separati da uno spazio, che indicano rispettivamente la dimensione dell’array e il numero di query.La seconda riga contiene
n interi positivi, rappresentanti gli elementi dell’array. Ciascun elemento è positivo e non supera .Le
q righe successive rappresentano le query. Ogni query è descritta da un tipo (1 o 2) seguito dai parametri necessari:- Per le query di tipo 1: un intero
s.
- Per le query di tipo 2: una posizione
pe un valorexda aggiornare all’indice corrispondente.
Output
Per ogni query di tipo 1, stampate
YES se esiste un sottoarray prefisso la cui somma è uguale a s, altrimenti stampate NO.Examples
Input | Output |
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