Good triangles#524

Good triangles (Editorial)

Крок 1: гарний відрізок не буває довгим. Припустимо, у мультимножині немає жодного трикутника. Відсортуємо її: b_1 \le b_2 \le \ldots \le b_k. Відомий факт — трикутник існує тоді й лише тоді, коли його утворює якась трійка сусідніх у відсортованому порядку елементів. Отже для всіх маємо b_i + b_{i+1} \le b_{i+2}, тобто послідовність росте не повільніше за числа Фібоначчі:

b_k \;\ge\; F_k \quad (F_1 = F_2 = 1).

Оскільки a_i \le 10^6, а F_{31} = 1\,346\,269 > 10^6, у поганому наборі не може бути більше ніж елементів. Висновок:

будь-який відрізок довжини автоматично гарний.

Тому визначимо — найменший правий кінець (точніше, позиція одразу за ним), для якого a[i..\mathrm{nx}[i]-1] вже гарний. Шукати його треба не далі ніж на крок уперед: додаємо елементи по одному у відсортований буфер (вставкою, буфер крихітний) і після кожного перевіряємо трійки сусідів, яких торкнулася вставка. Один коштує \mathcal{O}(L^2) при L \approx 35 — дрібниця.

Крок 2: жадібність оптимальна. Щоб отримати максимум частин, кожну частину слід робити якнайкоротшою: стоячи в позиції , беремо блок [\,i,\ \mathrm{nx}[i]-1\,] і стрибаємо в . Це коректно, бо гарність монотонна: відрізок, що містить гарний відрізок, теж гарний. Тому будь-яке розбиття можна крок за кроком «підтиснути» до жадібного, не зменшивши кількості частин.

Залишок теж не проблема. Якщо після стрибків ми опинилися в позиції p \le r, а далі стрибнути вже не виходить, то хвіст просто приклеюємо до останнього блоку — він від цього гарним бути не перестане. Отже

\text{відповідь} = \#\{\text{стрибків із } l, \text{ що не виводять за } r+1\},

і нуль, якщо не вийшло жодного.

Крок 3: стрибки із оновленнями. Наївно крутити цикл — до r - l ітерацій на запит. Прискоримо звичним «стисканням шляху» в дереві відрізків. У вузлі, що покриває [lo, hi), для кожного стартового зсуву зберігаємо пару

\bigl(\mathrm{cnt}[k],\ \mathrm{last}[k]\bigr) = \text{(скільки повних блоків укладається, де опинимось), якщо стартувати з } lo + k \text{ і не виходити за } hi.

Злиття дітей очевидне: проходимо ланцюжок у лівій дитині, а якщо він упирається в межу — продовжуємо з відповідного зсуву в правій.

Ключова економія: у кожному вузлі достатньо зберігати лише перші L \approx 35 зсувів. Справді, у канонічному розкладі запиту перший вузол починається рівно в , а в кожен наступний ми входимо після стрибка, який «перелетів» його ліву межу менш ніж на — бо довжина блока менша за . Тому зсуви, більші за , ніколи не питають. Розмір структури — , злиття вузла — .

Оновлення. Зміна a_i псує лише ті , у яких j \in (i - L,\ i]. Перераховуємо їх, і якщо якісь справді змінилися — переззливаємо вузли на шляхах до цих листків: \mathcal{O}(L \log n).

Запит. Ідемо по \mathcal{O}(\log n) вузлах розкладу зліва направо, тягнучи за собою пару (кількість, поточна позиція). Якщо поточна позиція ще не дійшла до вузла — робимо один явний стрибок , інакше беремо готову пару за зсувом. Разом \mathcal{O}(\log n) на запит.

Підсумок: \mathcal{O}(nL + q L \log n). При n, q \le 5 \cdot 10^5 це проходить, але вимагає швидкого вводу-виводу та компактних масивів (пари краще тримати в плоских масивах, а не у векторі структур).