Запити по значеннях (Розбір)

Основна ідея

Розглянемо два сусідні входження однакового значення $x$ на позиціях $i$ та $j$, тобто

Спочатку кожен елемент зі значенням $x$ можна вважати таким, що потребує окремої операції. Проте іноді два сусідні входження $x$ можна занулити в межах однієї й тієї самої послідовності операцій, тобто друге входження не збільшує відповідь.

Це можливо тоді і тільки тоді, коли для всіх позицій $k$, таких що i<k<j, виконуються дві умови:

1. a_k>x;

2. a_k\le R.

Перша умова означає, що між двома однаковими значеннями $x$ немає елемента, який стане нулем раніше або одночасно з ними та не дозволить об'єднати ці два входження.

Друга умова означає, що всі елементи між ними взагалі дозволено змінювати в поточному запиті. Оскільки x\in[L,R] та всі проміжні значення строго більші за $x$, нижня межа $L$ для них виконується автоматично. Тому достатньо перевіряти лише верхню межу $R$.

Позначимо через cnt_x кількість елементів масиву, рівних $x$. Початково встановимо

Значення res_x означатиме кількість операцій, яку додають до відповіді елементи зі значенням $x$.

Кожного разу, коли два сусідні входження $x$ можна об'єднати, значення res_x зменшується на $1$.

Перша умова

Будемо проходити масив зліва направо та підтримувати pos_x — останню позицію, на якій зустрічалося значення $x$.

Нехай поточна позиція дорівнює $j$, a_j=x, а попереднє входження $x$ знаходиться на позиції

Потрібно перевірити, що

Мінімум на проміжку можна знаходити за допомогою дерева відрізків.

Важливо, що потрібно брати саме проміжок

не включаючи самі позиції $i$ та $j$, оскільки на них значення дорівнює $x$.

Якщо i+1>j-1, тобто два однакові елементи стоять поруч, ця умова виконується автоматично.

Якщо попереднього входження $x$ не існує, то об'єднувати поточний елемент немає з чим.

Друга умова

Для кожної пари сусідніх входжень $x$, яка пройшла першу перевірку, знайдемо

Така пара може бути об'єднана в запиті тоді і тільки тоді, коли

Отже, кожній допустимій парі поставимо у відповідність подію

Подія означає, що починаючи з усіх запитів з R\ge mx можна зменшити

на одиницю.

Відсортуємо всі події за $mx$, а всі запити — за правою межею $R$.

Будемо обробляти запити у порядку зростання $R$. Перед відповіддю на черговий запит активуємо всі події, для яких

При активації події $(mx,x)$ виконуємо

Відповідь на запит

Для запиту $[L,R]$ нас цікавлять лише початкові значення, що належать цьому проміжку.

Тому відповідь дорівнює

Для підтримки масиву $res$ використаємо дерево Фенвіка або дерево відрізків.

Спочатку в позицію $x$ записуємо cnt_x. При активації події робимо точкове оновлення на $-1$, а для кожного запиту знаходимо суму на проміжку $[L,R]$.

Таким чином, усі запити можна обробити офлайн.

Загальна асимптотика — O((n+q)\log n).

Використання пам'яті — O(n+q).