ВузАк 2024-2025 Финал Задача A Часть 2/3 2026-07-01

Задача A. K-интересные подотрезки Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт В древнем королевстве Бурляндия мудрый математик Вася открыл таинственное свойство некоторых массивов. Согласно древним свиткам, k-интересные массивы содержат ключ к поиску скрытых сокровищ по всему королевству. Вася определяет массив a длины n как k-интересный, если существует такой индекс i (1 ≤ i меньше n), что: (a1 + a2 + ... + ai) · a(i+1) · a(i+2) · ... · an = k Иными словами, сумма первых i элементов, умноженная на произведение оставшихся элементов, равна k. Король Артур, очарованный этими массивами, владеет картой, представленной в виде массива длины n. Он подозревает, что некоторые части этой карты могут привести к различным сокровищам, каждое из которых связано с определенным значением k. Королевские советники подготовили q запросов для анализа этой карты. Всего есть два типа запросов. Каждый запрос первого типа задаётся тремя числами l, r и k. Ваша задача — проверить, правда ли, что подмассив массива a с l-го по r-й элементы является k-интересным. Кроме того, советники иногда обновляют карту новой информацией. Эти обновления представлены как запросы второго типа. Каждый запрос второго типа задан двумя числами i и x, которые обозначают, что теперь i-й элемент массива a равен x. Помогите королю Артуру найти сокровища до того, как их обнаружат другие королевства! Формат входных данных Первая строка содержит два целых числа n и q (2 ≤ n ≤ 2·10^5, 1 ≤ q ≤ 2·10^5) — длина массива a и количество запросов. Вторая строка содержит n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 10^9) — элементы массива a. Каждая из следующих q строк описывает запрос в одном из следующих форматов: 1 l r k — нужно проверить, является ли подмассив [l; r] массива a k-интересным (1 ≤ l меньше r ≤ n, 1 ≤ k ≤ 10^18). 2 i x — нужно присвоить ai значение x (1 ≤ i ≤ n, 1 ≤ x ≤ 10^9). Формат выходных данных Для каждого запроса первого типа выведите «YES», если указанный подмассив является k-интересным, или «NO» в противном случае. Система оценки Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой и необходимых подзадач успешно пройдены. Подзадача Баллы Доп. ограничения Необх. подзадачи 1 12 n, q ≤ 200 - 2 9 n ≤ 200, запросы только 1-го типа - 3 14 n, q ≤ 3000, запросы только 1-го типа - 4 7 n, q ≤ 3000 1, 3 5 15 В любой момент ai четно, запросы только 1-го типа - 6 12 В любой момент ai четно 5 7 20 Запросы только 1-го типа 2, 3, 5 8 11 — 1,2,3,4,5,6,7 Примеры Пример 1 Ввод: 5 4 5 2 7 10 2 1 2 4 90 2 4 11 1 2 4 90 1 1 5 308 Вывод: YES NO YES Пример 2 Ввод: 7 6 4 6 4 2 9 10 7 2 7 3 2 4 8 1 3 4 32 2 7 7 2 3 10 1 4 6 720 Вывод: YES YES Замечание Разберем первый пример из условия. В первом запросе нас просят проверить, является ли подмассив [2, 7, 10] 90-интересным. Он является таковым, так как (2 + 7) · 10 = 90. После второго запроса массив выглядит следующим образом: [5, 2, 7, 11, 2]. В третьем запросе нас просят проверить, является ли подмассив [2, 7, 11] 90-интересным. Он таковым не является, так как мы не можем выбрать такое i, чтобы произведение суммы первых i элементов и остальных элементов было равно 90. В четвертом запросе нас просят проверить, является ли массив целиком 308-интересным. Он является таковым, так как (5 + 2 + 7) · 11 · 2 = 308. 0:00 – Введение: повторение условия задачи, два случая (справа все единицы или есть элементы больше 1) 5:26 – Второй случай: итеративный перебор справа налево, накопление произведения правой части (multR) 10:59 – Итеративная сумма на подотрезке: обход снизу, правила взятия левых (нечётных) и правых (чётных) узлов 18:27 – Введение операции find_first: поиск первого индекса, начиная с L, где сумма ≥ target 28:00 – Рекурсивная реализация find_first: аргументы (узел, TL, TR, L, target), введение секретной переменной add (накопленная сумма) 45:46 – Переработка дизайна функции: уточнение условий (листик, полное попадание, нехватка), обновление add при нехватке 1:02:50 – Тестирование функции на запросе L=5, target=20 с пошаговым разбором рекурсивных спусков и возвратов 1:17:21 – Заключение: домашнее задание (написать и протестировать find_first на случайных данных, сравнить с наивным алгоритмом)