Відновлення масивів#24

Відновлення масивів (Editorial)

Кожен запит [f, s, X] означає \min(a_f, a_s) = X, тобто одночасно два факти: обидва елементи не менші за , і хоча б один із них дорівнює .

Перша частина дає природну нижню межу. Покладемо

a_i = \max\{X_j : \text{запит } j \text{ згадує індекс } i\},

а для індексів, які не згадуються в жодному запиті, візьмемо будь-яке допустиме значення, наприклад 10^9.

Виявляється, цього достатньо — отриманий масив задовольняє всі запити, а не лише нерівності. Доведемо це.

Умова гарантує, що якийсь коректний масив існує. Для нього виконуються всі нерівності b_f \ge X, тому b_i \ge a_i для кожного (адже a_i — максимум саме цих нижніх меж).

Тепер візьмемо довільний запит [f, s, X] і припустимо, що наша побудова його порушує, тобто a_f > X і a_s > X. З a_f > X випливає b_f \ge a_f > X. Але для масиву виконано \min(b_f, b_s) = X, тому мусить бути b_s = X. Тоді a_s \le b_s = X, що суперечить припущенню a_s > X. Отже, порушення неможливе.

Реалізація тривіальна: заводимо масив нулів, для кожного запиту робимо a_f \leftarrow \max(a_f, X) і a_s \leftarrow \max(a_s, X), а на виході замінюємо нулі на 10^9 (елементи мають бути натуральними й не перевищувати 10^9).

Складність — \mathcal{O}(N + M).