Якщо \(l_1 > 1\) та \(l_2 > 1\), то відповідь 1. Тепер припустимо \(l_1=1\), тоді якщо \(l_2>r_1+1\), то відповідь рівна \(r_1+1\), інакше \(max(r_1, r_2)+1\).
Іншим розв’язком буде побачити, що відповідь може бути лише 1, \(r_1+1\) або \(r_2+1\). Ми можемо спробувати усі 3 варіанти та вибрати найменший.
Погрупуємо усі улюблені рядки за кількістю символів B
всередині. Неважко зрозуміти, що кожній такій групі буде відповідати
підрядок у рядку-відповіді, який буде складатись із відповідної
кількості символів B. Між такими рядками слід поставити
\(max(a, c)\) символів A,
а з лівого та правого краю по \(a\) та
\(c\) відповідно. Тому, відповідь це
\((1 + 2 + ... + b) + max(a,c) \cdot (b-1) + a
+ c = \frac{b(b+1)}{2} + max(a,c) \cdot (b-1) + a + c\).
Розглянемо такий індекс \(i\), де досягається мінімум \(|a_i-b_i|\). Поставимо на \(i\)-ту позицію різні значення в обидвох стрічках.
Для усіх інших позицій поставимо однакові значення в обох стрічках такі, щоб ми не обрали жодного значення з проміжку \([min(a_i, b_i), max(a_i, b_i)]\). Зауважимо, що не можливо, щоб для певного \(j\) і \(a_j\) і \(b_j\) були з цього проміжку, адже тоді значення \(|a_j-b_j|\) буде меншим за \(|a_i-b_i|\).
Тож відносний порядок не зміниться якщо в проміжному масиві замінити \(a_i\) на \(b_i\), оскільки не обрано жодного іншого значення між ними.
Знайдемо вершину з найменшою відстанню, яка відома. Якщо такої немає, то заданий граф — бамбук, і відповідь це обидва його кінці. Якщо така є, і її відстань дорівнює 1, то можна перебрати усіх сусідів, для яких невідома відстань та за \(O(n+m)\) використовуючи bfs перевірити, чи може вона бути відповіддю. Оскільки сусідні до цієї вершини ребра можуть проходити лише на сусідні відстані, таких вершин не може бути більше ніж 3.
Розглянемо тепер випадок, коли відстань до цієї вершини більша за 1. Неважко побачити, що вершини з невідомими відстанями та ребра між ними утворюють набір графів-бамбуків, оскільки ребра між ними можуть проходити лише між сусідніми значеннями відстані, і для кожної відстані є лише одна невідома вершина. Тож, як і в попередньому випадку, переберемо усіх невідомих синів знайденої вершини, і перевіримо для кожного із них обидва кінці бамбука, якому вона належить.
Отже, загальна складність: \(O(n+m)\).
Розглянемо найнижчу стіну, серед однакових візьмемо найлівішу. Нехай вона знаходиться на позиції \(i\), її висота \(a\). Щоб для цієї стіни виконувалась умова, необхідно, щоб у всіх правіших стінах була хоча б одна дірка на висоті не більшій \(a\). Зробимо дірку на висоті \(a\) у всіх правіших стінах висота яких більша за \(a\). Тоді для всіх стін правіше необхідна умова також виконується, крім того, ми зробили мінімальну можливу кількість дірок, адже ми не робили дірки у всіх стінках висоти \(a\).
Тепер розглянемо найнижчу стінку лівіше від \(i\). Нехай вона знаходиться на позиції \(j<i\), її висота \(b>a\). Є 2 варіанти, що робити:
Зробимо дірку на висоті \(a\) у всіх стінках від \(j\) до \(i\).
Зробимо дірку на висоті \(b\) у всіх вищих за \(b\) правіше стінки \(j\).
Порахуємо, який варіант робить меншу кількість дірок. Далі розглянемо наступну найменшу стінку лівіше від \(j\). Для неї буде також 2 варіанти: або робимо дірки на тій же висоті, що й для \(j\)-ої стінки на проміжку до \(j\), або робимо дірки на висоті самої стінки у всіх вищих правіше неї. Якщо ми обираємо двічі підряд перших варіант, то необхідно зробити ще одну дірку в стіні \(j\) на висоті \(a\).
Тож розв’язком буде кожного разу робити меншу кількість дірок, враховуючи можливо 1 додаткову. Якщо обидва варіанти однакові варто обирати другий, адже тоді ми точно не будемо робити додаткову дірку.
Складність такого розв’язку \(O(n \log (n))\).
Проміжки, які повністю знаходяться лівіше (правіше) за \(x\) дають обмеження на те, що лівий (правий) край відповіді не повинен переходити за їх середину. Тому їх усіх можна опрацювати окремо підтримуючи в сеті усі обмеження зліва та справа.
Розглянемо тепер усі інші проміжки. Якщо середина якогось проміжку \(\frac{l+r}{2}\) знаходиться лівіше (правіше) за \(x\), то це означає, що якщо наша відповідь більша за половину довжини \(\frac{r-l}{2}\), то лівий (правий) край повинен бути не лівіше (не правіше) за середину. Якщо ж середина проміжку попадає в \(x\), то або лівий чи правий край буде в точці \(x\) та цей проміжок не накладе обмеження, або в протилежному разі, довжина проміжку відповіді не повинна перевищувати половину довжини проміжку.
Використовуючи описані вище факти, відповідь можна знаходити за допомогою бінарного пошуку, в якому для поточної довжини потрібно вміти знаходити найменші обмеження як зліва, так і справа. Це можна зробити за допомогою підтримки дерева відрізків для знаходження мінімуму на префіксі.
Розглянемо 2 пари \((a_1, b_1)\) та \((a_2, b_2)\) та спробуємо зрозуміти, чи можуть вони обидві одночасно бути успішними. Нехай \(dist(a_1, b_1) \ge dist(a_2, b_2)\), тоді спершу успішною повинна стати перша пара, далі друга, адже значення діаметра не може зростати при видаленні вершин. При рівності пари одночасно повинні стати успішними.
Нехай \(c_1\) — середина шляху від \(a_1\) до \(b_1\). Це може бути як вершина, так і ребро, для зручності будемо розглядати, що це вершина, для подальшого розв’язку це не має значення, а також явно знаходити \(c_1\) не буде потрібно. Видалимо всі вершини \(v\) такі, що \(dist(c_1, v) > dist(c_1, a_1)\). Після цього пара \((a_1, b_1)\) стала успішною. Тож коли ж зможе після цього стати успішною пара \((a_2, b_2)\)? Якщо не видалили жодну з цих вершин. Тобто можна перевірити, що \(dist(a_2, c_1) \le dist(a_1, c_1)\) та \(dist(b_2, c_1) \le dist(a_1, c_1)\). Цю умову також можна зробити без знаходження \(c_1\): достатньо перевірити, що усі значення \(dist(a_1, b_1)\), \(dist(a_1, b_2)\), \(dist(a_2, b_1)\) та \(dist(a_2, b_2)\) не більші за \(dist(a_1, b_1)\).
Зауважте також, якщо виконується умова, після того, як ми зробили успішною пару \((a_1, b_1)\) ми можемо зробити успішною пару \((a_2, b_2)\) залишивши усі вершини, які знаходяться не далі за \(dist(a_2, b_2) / 2\) від середини шляху між \(a_2\) і \(b_2\).
Тепер нехай у нас є багато пар, потрібно визначити, чи можливо зробити їх усіх успішними. Успішними вони можуть ставати в порядку за спаданням відстані між вершинами. Якщо є пари з однаковою довжиною, то вони повинні стати одночасно успішними, тому байдуже в якому порядку їх розглядати. Необхідну умову також достатньо перевіряти лише між сусідніми парами у такому порядку, адже ми зможемо завжди підтримувати умову, що залишаться усі вершини не дальші за половину відстані від центру.
Тепер, щоб відповідати на запити, порахуємо для кожного \(l\) таке найбільше \(R_l\), що ми можемо зробити усі пари від \(l\) до \(R_l\) успішними. Зрозуміло, що для усіх \(r<R_l\) усі пари від \(l\) до \(r\) також можна зробити успішними. Будемо робити це методом 2 вказівників, а також підтримувати сет пар посортованих за відстанню, де між кожною парою сусідніх пар будемо перевіряти умову.
Складність такого розв’язку \(O(n \log n)\).