Возвращение к домашней работе

Будем хранить строку в персистентном декартовом дереве, где одна вершина соответствует одному символу, в вершине хранится флаг, означающий, развернуто ли ее поддерево. Также, будем хранить в каждой вершине матрицу d размера 4 × 4, где dij — длина самой большой монотонной последовательности, начинающейся с числа i и заканчивающаяся числом j (i может быть больше j).

Чтобы найти длину последовательности в поддереве, если строка не развернута, нужно взять , а если развернута, .

Чтобы дублировать строку, воспользуемся тем, что декартово дерево персистентно. Для начала, научимся удваивать строку. Пусть мы хотим удвоить строку, которой соответствует поддерево вершины v. Тогда, для этого нужно сделать операцию merge вершины v самой с собой. Персистентное дерево позволяет это сделать, потому что оно никогда не меняет старые вершины, а всегда создает их копии. Для того, чтобы продублировать строку s k раз, нужно, как в бинарном возведении в степень, получить строку s, продублированную 20 раз, 21 раз, 22 раз, 23 раз, и так далее. А потом сделать операцию merge логарифма нужных из данных строк.