It's not Time for Games#208

It's not Time for Games (Editorial)

Ключове спостереження в умові: коли людина виходить, індекси не зсуваються і нові пари не утворюються. Тому множина можливих пар з часом лише звужується, а самі значення пар не змінюються.

Позначимо s_i = a_i + a_{i+1} — рівень пари сусідів та i+1 (для 1 \le i \le n-1). Окремо є «замикаюча» пара кола: s_{\text{кільце}} = a_n + a_1.

У момент часу коло вже покинули люди з номерами 1, 2, \ldots, t. Пара (i, i+1) уціліла тоді й лише тоді, коли обидва її учасники ще на місці, тобто коли i \ge t+1. Отже, відповідь на запит — це

\max_{t+1 \le i \le n-1} s_i.

Пара потребує окремої уваги: вона існує лише доки людина не пішла, тобто тільки при t = 0. Це найлегше проґавити.

Щоб відповідати на запити швидко, порахуємо суфіксні максимуми: \mathrm{suf}[i] = \max(s_i, \mathrm{suf}[i+1]), ідучи від i = n-1 до . Тоді кожен запит обробляється за : беремо \mathrm{suf}[t+1], а при t = 0 додатково порівнюємо з a_n + a_1.

Умова гарантує t < n-1, тому хоча б одна пара завжди залишається і відповідь визначена. Загальна складність — \mathcal{O}(n + q).