Множення запитів#496

Множення запитів (Розбір)

Автор, розробник, автор розбору: Тимур Дегтеарі

Цю задачу можна ефективно вирішити, використовуючи два ключові спостереження.

  1. Монотонність значень: Оскільки x_i \ge 1, як тільки a_j \ge Y після -го оновлення, воно залишиться таким після всіх наступних оновлень. Тому достатньо визначити, для кожного індексу , перше оновлення, після якого a_j \ge Y. Якщо ми позначимо номер цього оновлення як , то остаточна відповідь буде простою: b_j = q - f(j) + 1.

  2. Обмежена кількість значущих оновлень: Оновлення з x_i = 1 взагалі не змінюють масив , тому ми можемо їх пропустити. Для оновлень з x_i \ge 2, кожен елемент, на який це впливає, принаймні подвоює своє значення. Відповідно, будь-який елемент може бути суттєво змінений максимум \log_2(Y) таких оновлень, перш ніж досягти або перевищити .

Ми підтримуємо множину , що містить усі індекси , для яких a_j < Y. При обробці оновлення з x_i \ge 2:

  • Перебираємо всі індекси j \in S, які лежать у діапазоні [l_i, r_i].

  • Множимо a_j на x_i.

  • Якщо a_j \ge Y після множення, записуємо f(j) = i і видаляємо з (оскільки всі майбутні оновлення збережуть a_j \ge Y).

На перший погляд, цей підхід може здаватися O(q \cdot n). Однак, згідно з спостереженням (2), кожен елемент може бути відвіданий максимум \log_2(Y) разів протягом усіх оновлень (оскільки кожне відвідування принаймні подвоює його значення). Використовуючи збалансовану структуру даних (таку як std::set) для ефективного запиту елементів у діапазоні, загальна складність стає:

[O(q (n) + n _2(Y))]

Це достатньо ефективно з урахуванням обмежень задачі.