Prefix Sum Query (Präfixsummen-Abfrage)
Sie haben ein Array aus
n positiven ganzen Zahlen. Ihre Aufgabe ist es, q Abfragen zu bearbeiten, wobei jede Abfrage einen von zwei Typen haben kann:- Überprüfen Sie, ob es im gegebenen Array ein Präfix-Teilarray (also ein Teilarray von Beginn des Arrays an) gibt, dessen Summe einem gegebenen Wert
sentspricht.
- Aktualisieren Sie den Wert an einem bestimmten Index im Array.
Schreiben Sie ein Programm, das diese Abfragen effizient beantwortet.
Eingabe
Die erste Zeile enthält zwei ganze Zahlen
n und q (1 ≤ n, q ≤ 100 000), getrennt durch ein Leerzeichen. Diese geben die Größe des Arrays und die Anzahl der Abfragen an.Die zweite Zeile enthält
n positive ganze Zahlen, welche die Elemente des Arrays darstellen. Jedes Element ist positiv und überschreitet nicht .Die nächsten
q Zeilen repräsentieren die Abfragen. Jede Abfrage wird durch den Abfragetyp (1 oder 2) gekennzeichnet und erfordert zusätzliche Parameter:- Für Abfragetyp 1: eine ganze Zahl
s.
- Für Abfragetyp 2: eine Position
p(Index) und einen Wertx, mit dem das Element an diesem Index aktualisiert wird.
Ausgabe
Für jede Abfrage vom Typ 1 geben Sie
YES aus, falls ein Präfix-Teilarray existiert, dessen Summe s entspricht. Andernfalls geben Sie NO aus.Beispiele
Eingabe | Ausgabe |
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