Здравствуйте, мне нужна помощь в решении следующей проблемы
v - последовательность длины k. За один шаг мы можем выбрать индекс i и изменить значение v_i на (v_i) - 1 или на (v_i) + 1.
У нас есть f (v_1, v_2, ..., v_k), которое является минимальным числом шагов для удовлетворения v_1 <= v_2 <= ... <= v_k. </p>
Нам дан массив s длины n.
Нам нужно ответить на q независимых запросов. Для каждого запроса нам даются значения a и b, и мы должны возвращать значение f (s_l, s_ {l + 1}, ..., s_r), где
l = ((a + last-1) mod n) +1 и r = ((b + last-1) mod n) +1, а last является ответом на предыдущий запрос. Для первого запроса l = a и r = b
1 <= N <= 100000 </p>
1 <= д <= 100000 </p>
1 <= s_i <= 32 </p>
Моя идея состояла в том, чтобы использовать очередь с приоритетами для вычисления f (s_l, s_ {l + 1}, ..., s_r) за O ((rl) log (rl)) времени, но это было медленным, поскольку это дает общее значение временная сложность O (qn logn) времени.
Может кто-нибудь мне помочь и подсказать более эффективный подход?