Жадность.

Во-первых давайте наш исходный массив превратим в в массив частичных сумм, тогда операцией является прибавить единичку в позиции i и вычесть единичку в позиции j > i. Причем j может быть равно n, то есть ничего в таком случае делать не надо.

Теперь жадность такая: идем слева направо и храним сколько единичек мы уже прибавили на префиксе, пытаемся очередное число "убить"(то есть повычитать из него единицы) уже имеющимися. Eсли этого сделать не можем, то вспоминаем какое самое большое число a мы "убили" раньше и если это число больше текущего, то возвращаем a, и прибавляем к ответу 4 - a, а к числу свободных 4. Иначе прибавляем к ответу 4 - cur и к числу свободных тоже 4 - cur, то есть мы это число не сможем убить выгодно для нас. Понятнее кодом объяснить. Функция solveGreedy.

It can be solved easily using cartesian tree. Store the vertices in DFS order. To process first query you just need to insert new node in CT right after it's parent. To answer other queries you need to get the subtree of the given node. You can do this by storing depths of each vertex and minimal depth in subtree. You should first split CT by given node(it should go to the left tree). Then find the leftest vertex in the right tree whose depth is lesser or equal to depth of the given node and split by this vertex. Now all the queris are just add on segment, get sum of segment and delete segment. This is a standard CT problem.