Харухи и путешествие на круге

Для удобства введем функцию $$$m(v)$$$ – диаметрально противоположный сектор сектору $$$v$$$ и $$$dist(u, v)$$$ – расстояние между 2 секторами без прыжков.

Идея 1. Не нужно прыгать больше одного раза.

Доказательство:

Пусть мы прыгнули больше одного раза, тогда мы прыгнули хотя бы 2 раза и часть пути будет состоять из переходов $$$u \to m(u) \to v \to m(v)$$$. Введем $$$c = m(v)$$$, тогда $$$v = m(c)$$$ и получаем путь $$$u \to m(u) \to m(c) \to c$$$, причем $$$dist(u, c) = dist(m(u), m(c))$$$, но тогда можно пойти напрямую из $$$u$$$ в $$$c$$$ и при этом сэкономить время: $$$dist(u, c) = dist(m(u), m(c)) < a_u + dist(m(u), m(c)) + a_{m(c)}$$$.

Из первой идеи следует, что нам достаточно рассмотреть единственный путь без прыжков и все пути ровно с одним прыжком. Будем далее считать, что мы совершаем ровно один прыжок. Если лучший ответ с одним прыжком $$$ans_1$$$, то ответом на запрос будет $$$\min (dist(u, v), ans_1)$$$.

Идея 2. Все пути ровно с одним прыжком можно рассмотреть с помощью 3 деревьев отрезков на минимум (далее ДО).

Построим 3 дерева отрезков:

1. ДО по массиву $$$a$$$.
2. ДО по массиву $$$b: b_i = a_i + 2 \cdot i$$$.
3. ДО по массиву $$$c: c_i = a_i - 2 \cdot i$$$.

Для ответа на запрос $$$u, v$$$ поделим окружность на 4 части сегментами $$$u, v, m(u), m(v)$$$, причем сегменты делящие окружность можно отнести к любой из частей. Рассмотрим произвольный путь с 1 прыжком и начнем двигать место прыжка по часовой стрелке, то есть рассмотрим все пути вида $$$u \to c \to m(c) \to v$$$. Очевидно, что от $$$u$$$ до $$$c$$$ и от $$$m(c)$$$ до $$$v$$$ нужно идти по кратчайшему пути. Тогда временем затраченным на такой путь будет $$$f(c) = dist(u, c) + dist(m(c), v) + a_c$$$. При изменении $$$c$$$ на 1 изменения слагаемых $$$dist(u, c)$$$ и $$$dist(m(c), v)$$$ будет либо +1, либо -1, а значит эти слагаемые либо увеличат расстояние на 2, либо уменьшат на 2, либо не изменят сумму, а слагаемое $$$a_c$$$ просто зависит от $$$c$$$, но ведь это и есть 3 возможных поведения массивов, на которых построено ДО. Можно доказать, что внутри одной из четырех частей, на которые мы поделили окружнсоть, изменения $$$f$$$ будут соответствовать одному из 3 типов ДО, а реальное значение совпадать с точностью до константы, которую можно вычислить по заданным $$$u, v$$$. Самый простой способ вычислить константу без использования формул – посчитать значение $$$f$$$ в одной точке каждой из частей и сравнить значение со значением в этой же точке в нужном типе ДО (выбор нужного типа ДО по точке оставляется как упражнение читателю), например, пусть $$$b_c = x$$$, $$$f(c) = y$$$, тогда внутри этой части будет выполняться $$$f(t) = b_t + (f(c) - b_c) = b_t + y - x$$$.

Доказательство того, что внутри одной из частей поведение не меняется:

Функция $$$dist(u, c)$$$ меняет поведение после прохождения точки $$$c = u$$$ и $$$c = m(u)$$$, а для $$$dist(m(c), v)$$$ после точек $$$m(c) = v$$$ и $$$m(c) = m(v)$$$, что равносильно $$$c = m(v)$$$ и $$$c = v$$$. Тогда получаем 4 точки: $$$u, v, m(u), m(v)$$$, после которых функция $$$dist(u, c) + dist(m(c), v)$$$ меняет поведение. Отсюда и следует неизменность поведения внутри одной из частей.