Задача из ШАДа.

Так как скоро вступительные в ШАД я решил разобрать вам задачу из 2023 года.
Еще больше полезного материала можно найти здесь

Решение:
В задаче якобы просят построить граф, но по факту вас интересуют только степени вершин. Давайте обойдемся без построения графа.
И так для каждой вершины k мы должны провести ребра к вершинам k-v[k], k - v[k] + 1, ...., k - 1. Проводить ребра явно плохая идея так как получим асимптотику O(n^2). Давайте мыслить в сторону степеней вершин. У каждой вершине на отрезке [k-v[k], k - 1] мы увеличиваем степень на один, а у вершины k степень увеличивается v[k].
Хочется применить дерево фенвика или дерево отрезков ?
- В целом можно но за это у вас снимут пару баллов, так как асимптотика такого решения O(n * logn).

Давайте придумаем решение за O(n).
Заведем массив ans размера n, давайте для каждой вершины k мы обновим массив ans следующим образом:
ans[k - v[k]] += 1
ans[k] -= 1
Этим трюком мы условно говорим " Давай прибавим +1 на отрезке [k-v[k], n - 1] (то есть на суффиксе, а также -1 на отерзке [k, n-1]"

После того как проделали для каждого k (0 <= k < n) мы посчитаем префикс сумму массива ans.
Осталось вывести массив ans[0] + v[0], ans[1] + v[1], ans[2] + v[2], ..., ans[n-1] + v[n-1].
Время работы алгоритма O(n)


Код в комментариях.