Магiчний набiр#166

Магiчний набiр (Розбір)

Спершу пригадаємо класичний факт про відрізки: набір відрізків має спільну точку попарно тоді й лише тоді, коли він має спільну точку всі разом. А це рівносильно простій умові

\max_i l_i \le \min_i r_i.

Справді, якщо максимум лівих кінців не перевищує мінімуму правих, то будь-яка точка між ними належить усім відрізкам; і навпаки, якщо \max l > \min r, то відрізок з найбільшим лівим кінцем і відрізок з найменшим правим не перетинаються.

Отже, задача звелася до такого: серед N+1 відрізків знайти той, після видалення якого виконується \max l \le \min r.

Перебирати кандидата й щоразу перераховувати максимум і мінімум з нуля — це \mathcal{O}(N^2). Замість цього скористаємось префіксними та суфіксними величинами. Порахуємо:

  • , — максимум лівих і мінімум правих кінців серед перших відрізків;

  • , — те саме для відрізків з -го до останнього.

Тоді після видалення відрізка отримуємо

\max l = \max(\mathrm{prefL}[i-1],\ \mathrm{sufL}[i+1]), \qquad \min r = \min(\mathrm{prefR}[i-1],\ \mathrm{sufR}[i+1]),

і умову перевіряємо за .

Загальна складність — . Якщо підходять кілька відрізків, виводьте будь-який згідно з форматом умови.