Three Queries#384

Three Queries (Editorial)

Автор задачі:

Костянтин Денисов

Задачу підготував:

Павло Цікалишин

Розбір написав:

Костянтин Денисов

Будемо розв'язувати нашу задачу в офлайні. Тобто зчитаємо наші запити наперед і будемо відповідати на них в зручному нам порядку.

Спершу зробимо стиск можливих значень масиву . Тобто відсортуємо масив унікальних можливих значень елементів масиву за час всіх запитів та змінимо всі значення b_i на . Таким чином отримаємо відносно невеликі значення масиву : 0 \le a_i < n + q.

Будемо обробляти запити по блоках розміром . Основна ідея полягає в тому, що ми розділяємо всі значення у межах поточного блоку на дві групи:

  • Особливі значення — це значення чисел нашого масиву, які змінювалися хоча б один раз у поточному блоці. Мається на увазі, що — особливе що змінювалося w_y під час блоку або в якийсь момент був запит третього типу з t=y, або був запит третього, що виконувалось a_x=y до запиту.

  • Неособливі значення — це всі інші значення.

Кількість особливих значень у кожному блоці обмежена не перевищує C \cdot 2, що дозволяє опрацьовувати їх окремо для кожного запиту. А неособливих значень не так мало, але їх перевага в тому, що для цих значень нічого не змінюється під час блоку, що дозволить їх зручно обробити.

Для кожного особливого значення :

  1. Знаходимо всі позиції, де воно знаходилося або могло знаходитися після оновлень у поточному блоці.

  2. Будемо проходитися по таких позиціях у порядку зростання.

  3. Одночасно з цим другим вказівником перебираємо запити, відсортовані за .

  4. Для поточного запиту перебираємо позиції, які менше або рівні за , з кінця поки не знайдемо позицію , де стоїть (поточне особливе значення) (щоб дізнаватися яке значення стоїть в тій позиції на момент запиту, то можемо для позицій, де були запити третього типу підрахувати для всіх моментів часу у блоку їх значення, це займає C^2 додаткового часу та пам'яті).

  5. Якщо w[x] = 1 та last \ge l, то враховуємо його у підрахунку для поточного запиту.

Оскільки особливих значень не більше ніж С \cdot 2, тому цей підхід ефективний.

Оновлення неособливих значень відбувається наступним чином:

  1. Проходимо масивом зліва направо, оновлюючи останню позицію кожного числа. При цьому ігноруємо особливі значення.

  2. Якщо w[x] = 1, додаємо у поточну позицію та у попередню, де на поточному префіксі це число було (або нічого не робимо, якщо це перше входження такого числа).

  3. Другим вказівником будемо проходитися по запитах, які відсортовані за .

  4. Тоді дізнатися кількість унікальних неособливих чисел на відрізку [l, r] враховуючи, що ми обробили лише перші це те саме, що знайти суму на відрізку [l, r];

  5. Через те, що оновлень сумарно буде O(n \cdot \frac{q}{C}), а самих запитів лише , використовуємо sqrt-декомпозицію для оновлення точкових значень за і знаходження суми на відрізку за O(\sqrt{n}).

Оберемо C=\sqrt{q} і тоді рішення працює за O(n \cdot \sqrt{q}).