Типова задача на запити#235

Типова задача на запити (Розбір)

Спершу позбудемось ділення. Умова $avg (S) \leq C$ \mathrm{avg}(S) \le C для відрізка $S$ рівносильна

i \in S \sum (a_{i} - C) \leq 0.

\sum_{i \in S} (a_i - C) \le 0.

Тому одразу замінимо масив на $b_{i} = a_{i} - C$ b_i = a_i - C: тепер треба з'ясувати, чи існує відрізок довжини щонайменше $L$ із недодатною сумою.

Через префіксні суми $P$ це формулюється так: чи існує $r \geq L$ r \ge L, для якого

P_{r} - 0 \leq t \leq r - L max P_{t} \leq 0.

P_r - \max_{0 \le t \le r-L} P_t \;\le\; 0.

Перевірка робиться одним проходом за $O (n)$ : рухаємо $r$ і підтримуємо максимум префіксних сум із затримкою на $L$ позицій.

Тепер найважливіше спостереження цієї задачі. За умовою $x \geq 0$ x \ge 0, тобто кожен запит лише зменшує елементи масиву. Отже, середнє значення будь-якого відрізка з часом лише спадає, і якщо гарний відрізок одного разу з'явився, він уже нікуди не подінеться. Іншими словами, послідовність відповідей має вигляд «кілька NO, а далі самі YES» — вона монотонна.

Це дозволяє не перераховувати відповідь після кожного запиту, а знайти двійковим пошуком перший запит, після якого відповідь стає YES.

Для фіксованого $t$ стан масиву після перших $t$ запитів будується за $O (n + t)$ \mathcal{O}(n + t): усі віднімання на відрізках накопичуємо в різницевому масиві й один раз розгортаємо префіксною сумою. Далі виконуємо описану вище перевірку за $O (n)$ .

Загальна складність — $O ((n + q) lo g q)$ \mathcal{O}((n + q)\log q), що з запасом вкладається в обмеження.

Стежте за типами: сума сягає $2 \cdot 1 0^{5} \cdot (1 0^{9} + 2 \cdot 1 0^{5} \cdot 1 0^{7})$ 2 \cdot 10^5 \cdot (10^9 + 2 \cdot 10^5 \cdot 10^7), тому обов'язково 64-бітний тип, а краще перевірити оцінку й за потреби взяти ширший.