Запрос на префиксную сумму (Prefix Sum Query)
Вам дан массив из
n положительных чисел. Ваша задача — обработать q запросов, при этом каждый запрос может быть одного из двух типов:- Проверить, существует ли префиксный подмассив данного массива, сумма которого равна заданному значению
s.
- Обновить значение в массиве по конкретному индексу.
Напишите программу, которая будет эффективно отвечать на эти запросы.
Ввод
В первой строке заданы два целых числа
n и q (1 ≤ n, q ≤ 100 000), разделённые пробелом. Они представляют размер массива и количество запросов соответственно.Во второй строке содержатся
n положительных целых чисел — элементы массива. Каждое число является положительным и не превышает .В следующих
q строках находятся описания запросов. Каждый запрос задаётся типом (1 или 2), за которым следуют нужные параметры:- Для запроса типа 1: одно целое число
s.
- Для запроса типа 2: позиция
pи значениеx, которым нужно обновить элемент по этому индексу.
Вывод
Для каждого запроса типа 1 выведите
YES, если существует префиксный подмассив с суммой, равной s, или NO в противном случае.Примеры
Ввод | Вывод |
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