НВП (наибольшая возрастающая подпоследовательность) деген ең үлкен өсу қатары.

Түсінейік, \(b_i\) — позициясы \(i\)-де аяқталатын НВП ұзындығы және әрбір \(i\) үшін \(b_1 \oplus\ldots \oplus b_{i-1} \oplus b_{i+1} \oplus\ldots\oplus b_n\) мәнін есептеу керек.

Егер \(i\) позициясын алып тастасақ, онда оң жақтағы кейбір \(b_j\) мәндері максимум \(1\)-ге азаюы мүмкін. Бұл тек \(i\) позициясы \(j\)-де аяқталатын барлық НВП-де жатқан жағдайда ғана орын алады. Мұндай жағдайда \(i\) позициясы \(j\) позициясын доминациялайды деп айтылады.

Енді, егер \(i \to j\) бағытымен бағытталған қабырға жүргізсек, \(i\) позициясы \(j\) позициясын доминациялайды. Осылайша, бағытталған ацикликалық граф \(G\) аламыз.

Егер \(i < j < k\) және \(i \to k\) және \(j \to k\) қабырғалары бар болса, онда \(i \to j\) қабырғасы да бар болады деп түсінейік. Бұл дұрыс, себебі егер индекстер тізбегі \(p_1, \ldots, p_k\) \(p_k\) позициясы үшін НВП болса, онда \(p_1, \ldots, p_{k-1}\) \(p_{k-1}\) позициясы үшін НВП болып табылады. Сондықтан, бағытталған ағашты қалдыру жеткілікті. Формалды түрде, транзитивті жабуы \(G\)-мен сәйкес келетін минималды подграф ағаш болып табылады (позиция \(0\) түбірі деп санауға болады).

Осылайша, \(i\) позициясын жойғанда, дәл \(i\) шыңының подағашы өзгереді.

Енді, осындай ағашты қалай құру керектігін түсінейік. Барлық \(1, \ldots, i-1\) позициялары үшін ағашты құрдық деп алайық, енді \(i\) позициясының ата-анасын анықтаймыз. \(i\)-де аяқталатын НВП-ны ұзартуы мүмкін позициялар \(j_1, \ldots, j_k < i\) болсын, яғни \(j\) позициялары үшін келесі шарттар орындалады: \(j < i, a_j < a_i, b_j + 1 == b_i\). Сонда \(i\) позициясының ата-анасы \(\mathrm{lca}(j_1, \ldots, j_k)\)-ға тең болады, мұнда \(\mathrm{lca}\) — ең кіші ортақ ата-ана.

Осылайша, ағаш құру \(O(n \log(n))\) уақытта орындалады, ал жауапты қайта есептеу сызықтық уақытта жүзеге асырылады.

НВП – наибольшая возрастающая подпоследовательность.

Поймем что \(b_i =\) длина НВП кончающейся в позиции \(i\) и для каждого \(i\) нужно вычислить \(b_1 \oplus\ldots b_{i-1} \oplus b_{i+1} \oplus\ldots\oplus b_n\).

Если удалить позицию \(i\), то какие-то \(b_j\) справа могут уменьшиться максимум на \(1\). Произойдет это только в том случае, если позиция \(i\) лежит во всех НВП кончающихся в \(j\). Говорят, что \(i\) доминирует \(j\).

Проведем ребро из \(i \to j\) если \(i\) доминирует \(j\). Получим ориентированный ацикличный граф \(G\).

Поймем, что если \(i < j < k\) и есть ребра \(i \to k\) и \(j \to k\) то есть и ребро \(i \to j\). Это верно потому, что если последовательность индексов \(p_1,\ldots,p_k\) – НВП для позиции \(p_k\), то \(p_1,\ldots,p_{k-1}\) – НВП для позиции \(p_{k-1}\). Таким образом, достаточно оставить направленное дерево. Формально, минимальный подграф, чье транзитивное замыкание совпадает с \(G\) является деревом (можно считать что позиция \(0\) – корень).

Таким образом, при удалении позиции \(i\), изменится в точности поддерево вершины \(i\).

Осталось понять как строить такое дерево. Пусть мы построили дерево для всех позиции от \(1,\ldots, i-1\), хотим понять предка позиции \(i\). Пусть \(j_1,\ldots,j_k < i\) позиции которые могут удлиниться до НВП кончающейся в позиции \(i\), то есть набор позиций \(j\) для которых верно: \(j < i, a_j < a_i, b_{j} + 1 == b_i\). Тогда предок позиции \(i\) будет равен \(\mathrm{lca}(j_1,\ldots,j_k)\), где \(\mathrm{lca}\) – наименьший общий предок.

Таким образом, построения дерева работает за \(O(nlog(n))\) и пересчет ответа за линейное время.