Порахуйте кількість вкладених один в одного відрізків


Дізнайтесь більше про нові кар'єрні можливості в EchoUA. Цікаві проекти, ринкова оплата, гарний колектив. Надсилайте резюме та приєднуйтеся до нас.

На прямій дані N відрізків (у реальному житті це можуть бути проміжки часу, наприклад), які задані координатами їх лівого і правого кінця. Для кожного цього відрізку необхідно дізнатися, скільки з цих відрізків повністю знаходяться в нім. Один відрізок повністю міститься в другому, якщо лівий кінець першого відрізку знаходиться правіше за лівий кінець другого відрізку, а правий кінець першого знаходиться лівіше за правий кінець другий. Запропонуйте як можна ефективніший спосіб рішення цієї задачі. Гарантується, що усі кінці цих відрізків різні.

Якщо ви придумали рішення, то написати і перевірити його ви можете тут, на codeforces.

Рішення за О (n²) (повний перебір)

Давайте для кожного відрізку з набору перебером знайдемо усі відрізки, для яких виконується умова ” вкладеності”. Якщо так, то збільшимо відповідь для поточного відрізку, що розглядається нами, на одиницю. Нескладно зрозуміти, що це рішення працює за O (n²): для кожного з N відрізків ми перебираємо N відрізків. Чи можна швидше? Так!

Рішення за О (n log n) (сортування + структури даних)

Відсортуємо усі відрізки по лівому кінцю і розглядатимемо їх у вже відсортованому порядку. Згадаємо умову ” вкладеності”: лівий кінець першого відрізку правіший за лівий кінець другого відрізку, і правий кінець першого відрізку лівіший за правий кінець другого відрізку. Нескладно зрозуміти, що завдяки отсортированности усі ліві кінці ще нерасмотренных відрізків будуть правіші за лівий кінець даного відрізку. Таким чином, усі нерасмотренные відрізки потенційно є вкладеними в того, що розглядається: адже для них вже виконується одно з двох умов ” вкладеності” (про ліві кінці). Залишилося дізнатися, скільки з них дійсно є такими – для цього треба зрозуміти, скільки з нерозглянутих відрізків мають правий кінець лівіше за правий кінець даного відрізку.

Для цього підтримуватимемо структуру даних, яка може додати і видаляти з себе числа і відповідати на запити виду: “скільки чисел в мені менше X”?, причому усі операції повинні виконуватися за O (log n). Такою структурою даних може бути, наприклад, декартове дерево, дерево Фенвика, дерево відрізків, або tree з ext/pb ds/detail/standard policies.hpp (якщо ви пишете на З++). Перед виконанням алгоритму для вирішення завдання складемо в нашу структуру координати усіх правих кінців відрізків.

Тепер, щоб дізнатися скільки з нерозглянутих відрізків мають правий кінець лівіше за правий кінець даного відрізку, досить просто здійснити запит до структури даних “скільки чисел в тобі менше, ніж координата правого кінця даного відрізку”. Відповідь на цей запит і буде відповіддю для того, що розглядається на даний момент нами відрізок. Після запиту необхідно прибрати координату правого кінця відрізку із структури даних, щоб відповіді для усіх наступних відрізків були коректні: адже лівий кінець даного відрізку лівіше (завдяки отсортированности) лівий кінців усіх ще нерасмотренных відрізків.

Доведемо, що це рішення працює за О (n log n). Сортування усіх відрізків відбувається за O (n log n), складання усіх правих кінців відрізків в структуру даних за O (n log n), на стадії обчислення відповідей ми розглянемо n відрізків, для кожного з яких здійснимо два запити, обоє з яких виконаються за О (log n). Таким чином, обчислюємо усі відповіді ми за O (n log n) з препроцессингом за O (n log n), тобто і асимптотика усього рішення O (n log n).

Підвищуємо складність

Чи зможете ви вирішити ефективно це завдання у разі, якщо кінці відрізків можуть співпадати?

См також

Більше сайтів з подібними завданнями ви можете знайти в нашій підбірці.

Київ, Харків, Одеса, Дніпро, Запоріжжя, Кривий Ріг, Вінниця, Херсон, Черкаси, Житомир, Хмельницький, Чернівці, Рівне, Івано-Франківськ, Кременчук, Тернопіль, Луцьк, Ужгород, Кам'янець-Подільський, Стрий - за статистикою саме з цих міст програмісти найбільше переїжджають працювати до Львова. А Ви розглядаєте relocate?


Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *