Подарунки Васильку#503

Подарунки Васильку (Розбір)

Автор: Костянтин Денисов

Роздробник: Павло Цікалишин

Розбір підготовано: Костянтин Денисов

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

Поки будуємо :

  • поки |S|<m і i \le r, додаємо a_i в і i:=i+1;

  • інакше беремо мінімальний елемент з , записуємо в , і видаляємо його з .

На кожній позиції ми беремо найменше число, яке взагалі доступне зараз (тобто вже завантажене в пам'ять). Якщо на деякому кроці не взяти мінімум, то перша позиція, де ми відхилились, стане більшою — лексикографічно гірше.

2) Яка відповідь на -ту позицію. Позначимо len=r-l+1 і p=l+k+m-2 (це l+(k+m-1)-1).

  • Якщо p>r, тобто k+m-1>len, то робот встиг завантажити весь підмасив, і відповідь — просто -та порядкова статистика на [l,r]: b_k = k\text{-те найменше на }a[l..r].

  • Якщо p \le r, тоді відповідь така: b_k = \min\Bigl(a_p,\; k\text{-те найменше на }a[l..p]\Bigr).

Доведення формули індукцією по (випадок p \le r). Позначимо T(k)=l+k+m-2 (тобто T(k)=p) і — -те найменше на a[l..T(k)]. Твердження: b_k=\min(a_{T(k)},X(k)).

База k=1. До першого вибору робот може завантажити рівно елементів, тобто a[l..l+m-1]. Тому b_1 — мінімум серед цих елементів, а це рівно \min(a_{l+m-1}, 1\text{-ше найменше на }a[l..l+m-1]), тобто формула виконується.

Перехід k \to k+1. Припустимо, що після кроків робот видав b_1,\dots,b_k за формулою, і розглянемо крок k+1.

До моменту вибору (k+1)-го елемента робот може завантажити m+k перших елементів підмасиву, тобто рівно a[l..T(k+1)]. На перших кроках жадібний алгоритм завжди забирав мінімально можливе, отже він забрав рівно найменших елементів серед a[l..T(k+1)], окрім можливої заміни на a_{T(j)} там, де це було менше — але це якраз і означає, що на кроці k+1 серед кандидатів лишається:

  • або a_{T(k+1)}, якщо він виявився "дуже малим" і пробиває статистику,

  • або X(k+1) як найменший серед тих, що лишились після вилучення найменших.

Отже жадібний вибір на кроці k+1 дає b_{k+1}=\min(a_{T(k+1)},X(k+1)).

Таким чином твердження доведене для всіх .

Випадок p>r. Тут k+m-1>r-l+1, робот встигає завантажити весь , тому є просто відсортованим , і b_k — -те найменше на [l,r].

Як відповісти на запитів швидко.

Нам треба багато разів знаходити -те найменше число на відрізку . Для цього будуємо персистентне дерево відрізків по "значеннях", де в листках зберігаємо, скільки разів кожне значення зустрілося на префіксі.

1) Щоб були листки . Значення a_i великі, тому спочатку впорядковуємо всі елементи. Сортуємо пари (a_i,i) за a_i і замінюємо кожен a_i на номер його позиції у відсортованому списку (число від до ). Масив зберігає цей відсортований список: якщо листок має номер , то справжнє значення дорівнює d[pos].first.

2) Персистентні версії для префіксів. Будуємо корені c[0],c[1],\dots,c[n]. — це дерево для префікса .

У листку з номером зберігаємо число : скільки разів на префіксі зустрілося значення з номером .

У внутрішній вершині зберігаємо суму по її дітях (тобто скільки елементів префікса попадає в її діапазон листків).

Перехід від c[i-1] до : ми збільшуємо на значення в листку, що відповідає a_i. Персистентність означає: копіюємо тільки вершини на шляху від кореня до цього листка, і в них оновлюємо суми; всі інші вершини спільні з попередньою версією. Це O(\log n) нових вершин (функція add).

3) Як отримати відрізок з двох префіксів. Нехай ми хочемо працювати з підмасивом . Для будь-якого листка (тобто конкретного значення) кількість його появ на дорівнює: cnt_{[L,R]} = cnt_{[1,R]} - cnt_{[1,L-1]}, тобто різниця того самого листка в деревах і c[L-1].

4) Пошук -го найменшого. Маємо дві версії дерева: одна для префікса , друга для [1..L-1]. Розглянемо будь-яку вершину дерева, яка відповідає деякому діапазону значень . У цій вершині зберігається число елементів префікса, що попали в . Тоді кількість елементів на відрізку у цьому діапазоні дорівнює різниці цих чисел у двох версіях.

Щоб знайти -те найменше, спускаємося від кореня до листка. Нехай зараз ми в діапазоні і mid=(x+y)/2. Дивимось, скільки елементів з лежить у лівій половині : це різниця значень у лівих дочірніх вершинах двох версій. Позначимо це число як .

  • Якщо left \ge k, то шукане значення лежить у лівій половині, і ми переходимо в лівих дітей обох версій.

  • Інакше воно лежить у правій половині, тоді переходимо в правих дітей, а замінюємо на k-left.

Так ми за O(\log n) кроків дійдемо до листка, який і відповідає шуканому числу (потім переводимо його назад у початкове значення через відсортований список).

Складність. Побудова: додавань, кожне O(\log n), разом O(n\log n). Кожен запит: O(\log n). Пам'ять: O(n\log n) вершин.