Крок 1: гарний відрізок не буває довгим. Припустимо, у мультимножині немає жодного трикутника. Відсортуємо її: b_1 \le b_2 \le \ldots \le b_k. Відомий факт — трикутник існує тоді й лише тоді, коли його утворює якась трійка сусідніх у відсортованому порядку елементів. Отже для всіх маємо b_i + b_{i+1} \le b_{i+2}, тобто послідовність росте не повільніше за числа Фібоначчі:
Оскільки 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, а далі стрибнути вже не виходить, то хвіст просто приклеюємо до останнього блоку — він від цього гарним бути не перестане. Отже
і нуль, якщо не вийшло жодного.
Крок 3: стрибки із оновленнями. Наївно крутити цикл — до r - l ітерацій на запит. Прискоримо звичним «стисканням шляху» в дереві відрізків. У вузлі, що покриває [lo, 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 це проходить, але вимагає швидкого вводу-виводу та компактних масивів (пари краще тримати в плоских масивах, а не у векторі структур).