Послідовна мелодія#12997

Послідовна мелодія (Розбір)

Послідовний фрагмент повністю визначається своїм першим значенням : на позиції фрагмента [l, r] стоїть v + (i - l). Тому зручно ввести d_i = a_i - i для кожної відомої ноти.

Розглянемо два види фрагментів окремо.

Обидві частини рахуються одним проходом; масиви «перша відома праворуч» та «перша відома з іншим » будуються проходом справа наліво. Відповідь може сягати приблизно 3 \cdot 10^{17}, тож потрібен 64-бітний тип.

Складність: .

Для цього етапу офіційного розбору опубліковано не було; цей текст написано для архіву за розв'язком, який перевірено на задачі.