Формально, пускай нам дан массив $$$a$$$ размера $$$n$$$, такой, что для $$$0 \leq i \lt n$$$ верно $$$0 \leq a[i] \lt N$$$. Требуется найти длину наибольшей возрастающей подпоследовательности массива $$$a$$$

Конечно же решение использует метод динамического программирования. Мы будем рассматривать элементы $$$a[i]$$$ в порядке увеличения индекса $$$i$$$ и хранить массив $$$dp$$$ размера $$$N$$$, так, что $$$dp[x]$$$ равно наибольшей возрастающей подпоследовательности, последний элемент которой ровно $$$x$$$. Тогда, если массив рассчитан корректно для шага $$$i-1$$$, мы можем посчитать длину наибольшей возрастающей подпоследовательности, которая заканчивается в $$$a[i]$$$ как $$$cnt = 1 + \max\limits_{0 \leq x \lt a[i]} (dp[x])$$$, так как предыдущее число в подпоследовательности должно быть меньше $$$a[i]$$$. Теперь, если $$$cnt \gt dp[a[i]]$$$, нужно обновить $$$dp[a[i]] := cnt$$$

В процессе пересчёта массива $$$dp$$$ нам потребовалось две операции: получение максимума элементов массива на отрезке и изменение одного элемента. Обе эти операции можно делать деревом отрезков за $$$O(log(N))$$$ на одну операцию

Так как мы каждую операцию вызываем не более $$$n$$$ раз, получается сложность по времени $$$O(n \cdot log(N))$$$

Заметим, что мы могли итерироваться не по возрастанию индексов, а по убыванию, и считать длину наибольшей возрастающей подпоследовательности, которая начинается с элемента, равного x, а не начинается. Такой подход тоже даст верный ответ

Посмотрите "Решение задачи о нахождении LIS", чтобы понять, как обрабатывать удлинение префикса/суффикса

Если мы добавляем элемент $$$a[cur]$$$ к префиксу $$$A$$$, то нам нужно посчитать $$$cnt = 1 + \max\limits_{0 \leq x \lt a[cur]} sta[x]$$$. Если $$$cnt \gt sta[a[cur]]$$$, обновляем $$$sta[a[cur]] := cnt$$$

Если мы добавляем элемент $$$a[cur]$$$ к суффиксу $$$B$$$, то нам, аналогично, нужно посчитать $$$cnt = 1 + \max\limits_{a[cur] + 1 \leq y \lt N} stb[y]$$$. Если $$$cur \gt stb[a[cur]]$$$, обновляем $$$stb[a[cur]] := cnt$$$

Заметим, что когда мы удаляем элемент из префикса/суффикса, мы "откатываем" последнее обновление, которое сделали. А именно — увеличение максимума. Поэтому давайте придумаем, как хранить историю изменений прямо в Дереве отрезков

Давайте запоминать в листе Дерева отрезков не только текущее значение, но и все такие значения, которые не меньше своих предшественников. Будем хранить их в стэке, чтобы было удобно изменять значение на предыдущее. Теперь $$$sta[x]$$$ — это верхнее значение в вершине дерева, соответствующего индексу $$$x$$$. Изначально в стэке лежит только $$$0$$$

Теперь наша операция изменения распалась на две разные операции:

$$$add(x, val)$$$ — если $$$sta[x] \leq val$$$ — добавляем val в стэк вершины x сверху $$$del(x, val)$$$ — если $$$sta[x] == val$$$ — убираем из стэка вершины x элемент

А процедура удаления элемента $$$a[cur - 1]$$$ из префикса $$$A$$$ выглядит совсем просто. Посчитаем уже запомнившееся всем $$$cnt = 1 + \max\limits_{0 \leq x \lt a[cur - 1]} sta[x]$$$ — это ровно то значение, которое мы считали при добавлении $$$a[cur - 1]$$$ в префикс. Теперь если $$$sta[a[cur - 1]] == cnt$$$, значит мы делали соответствующее обновление операцией $$$add(a[cur - 1], cnt)$$$ и его нужно удалить со стэка, иначе значение не обновлялось и стэк трогать не нужно

Для массива $$$stb$$$ требуются аналогичные действия

Замечание. Попробуйте понять почему в операции $$$add$$$ нельзя заменить условие $$$sta[x] \leq val$$$ на $$$sta[x] \lt val$$$

Заметим, что если подпоследовательность проходит через $$$a[cur]$$$, то все её элементы в $$$A$$$ строго меньше $$$a[cur]$$$, а все элементы в $$$B$$$ строго больше, чем $$$a[cur]$$$

Из подсказки следует вывод о том, что длина такой последовательности равна $$$1 + \max\limits_{0 \leq x \lt a[cur]} sta[x] + \max\limits_{a[cur] + 1 \leq x \lt N} stb[x]$$$, так как часть такой подпоследовательности, находящейся в $$$A$$$, заканчивается на элемент $$$x \lt a[cur]$$$, а часть в $$$B$$$ начинается на элемент $$$y \gt a[cur]$$$. И $$$+1$$$ за счёт того, что сам элемент также участвует в последовательности

Обозначим последний элемент подпоследовательности, находящийся в $$$A$$$, через $$$x$$$. А первый элемент подпоследовательности, находящийся в $$$B$$$, через $$$y$$$. При этом $$$x \lt y$$$. Поэтому длина максимальной возрастающей подпоследовательности равна $$$\max\limits_{0 \leq x \lt y \lt N} sta[x] + stb[y]$$$

Давайте расположим естественным образом в квадрате $$$N \times N$$$ наши элементы $$$sta[x] + stb[y]$$$ — в клетке $$$(x, y)$$$ расположено значение $$$sta[x] + stb[y]$$$. Ниже на рисунке нарисована такая таблица и оба массива $$$sta$$$ и $$$stb$$$, в тех клетках, где $$$x \lt y$$$ написана сумма. Нам нужно вычислить максимум на таком треугольнике из клеточек

Почему задача поиска максимума на треугольнике не является очевидной? Каким был бы ответ, если бы нам нужно было найти максимум на прямоугольнике?

Для ответа на вопрос выше воспользуемся необычным устройством нашей таблицы. Если бы нам нужно было бы вычислить максимум на прямоугольнике $$$[lx, rx) \times [ly, ry)$$$, нужно было просто посчитать $$$\max\limits_{lx \leq x \lt rx} sta[x] + \max\limits_{ly \leq y \lt ry} stb[y]$$$, так как чтобы посчитать максимальную сумму в такой таблице — достаточно вычислить максимумы слагаемых

Можно ли воспользоваться этим свойством, чтобы свести задачу к более простой, если заметить большой прямоугольник внутри нашего треугольника?

Раз уж мы легко умеем считать максимум на прямоугольнике, давайте выделим большой прямоугольник слева сверху как на рисунке и посчитаем максимум на нём

Замечание. Так как в задаче в качестве $$$N$$$ мы можем выбрать любое число, большее $$$10^6$$$, давайте выберем степень двойки для удобства

Теперь ответ для большого треугольника представляется как максимум из ответа для прямоугольника и максимумов для маленьких оставшихся треугольничков — нижнего и правого, сторона которых в два раза меньше, чем у исходного

Запустим рекурсивный подсчёт, в котором будет $$$log(N)$$$ уровней. На первом уровне мы вычислим максимум на $$$1$$$ прямоугольнике, на втором уровне на $$$2$$$ прямоугольниках, на третьем на $$$4$$$-ех и так далее. Итого мы вычислим ответ на $$$O(N)$$$ (а если быть совсем уж точным, то на N — 1 прямоугольнике, смотри рисунок) прямоугольниках

Каждое вычисление работает за $$$O(log(N))$$$, так как у нас построены деревья отрезков на массивах $$$sta$$$ и $$$stb$$$. Итого пересчёт работает за $$$O(N \cdot log(N))$$$

Как избавиться от логарифмического множителя в асимптотике? Заметим, что он получается из-за запросов в Дерево Отрезков. А ещё заметим тот факт, что наши запросы имеют чёткую структуру

Обратим внимание на то, что так как при переходе к меньшему прямоугольнику мы делим сторону ровно пополам, ответ на наш запрос всегда целиком находится в одной вершине дерева отрезков для массива $$$sta$$$ и $$$stb$$$, поэтому максимум на таких отрезках мы можем вычислять за $$$O(1)$$$. Итого получается подсчёт максимума на треугольнике за $$$O(N)$$$

При таком действии в таблице меняется один столбец или одна строка. Сколько треугольников задевает такое изменение?

Наверняка Вы поняли по подсказке, что такое изменение задевает не более $$$log(N)$$$ треугольников, потому что строка или столбец пересекает максимум один треугольник на каждом уровне построения треугольников (ответ 4.3). Получается, теоретически возможно пересчитать ответ во всех изменившихся треугольниках за $$$O(log(N))$$$

Как же пересчитать ответ для всех изменившихся треугольников быстро?

Заметим, что если изменился маленький треугольник, то изменился треугольник вдвое большего размера, который его содержит. Тогда нам достаточно найти наименьший изменившийся треугольник и проитерироваться по всем содержащим его треугольникам. Кстати, это тоже можно реализовать через дерево отрезков

Тогда мы можем пересчитывать ответ за $$$O(log(N))$$$ на запрос, что нам и требовалось