04. Круговой RMQ#

📝 Условие#

Циклический массив. Запросы: прибавить v на дуге [l, r] и найти минимум на дуге [l, r].

📥 Входные данные#

В первой строке число n (1 ≤ n ≤ 2·10⁵). Во второй — n чисел a_0 … a_{n−1}. В третьей — число m операций. Далее m строк: lf rg — запрос минимума, lf rg v — прибавить v. Если lf > rg, отрезок идёт по кругу через конец массива.

📤 Выходные данные#

Для каждого запроса минимума — ответ на отдельной строке.

🧪 Тесты#

Тест 1#

Ввод:

4
1 2 3 4
4
3 0
3 0 -1
0 1
2 1

Вывод:

1
0
0

Тест 2#

Ввод:

3
5 -2 7
3
0 2
1 1 10
0 2

Вывод:

-2
5

Заметка

Оригинальное условие и проверка решения на всех тестах — по ссылке на источник.

💡 Подсказка#

⬅️ К списку задач уровня