Послідовність#270

Послідовність (Розбір)

Будемо йти зліва направо по масиву і тримати значення — максимальна довжина підпослідовності, що закінчується в елементі зі значенням . Тоді можна перераховувати dp_{a_i} = \max(dp_{a_i}, dp_j + 1), так що l \le j + a_i \le r.

Що робити тепер? Перераховуймо за допомогою дерева відрізків. Будемо запитувати максимум на відрізку [l-a_i;r-a_i], і оновлювати в точці a_i. Це можна робити за допомогою неявного дерева відрізків, або компресії координат.

Загальна асимптотика — з компресією.