В цій задачі можна просимулювати процес, описаний в умові, або ж посортувати масив і за один прохід знайти відповідь.
Неважко побачити, що, оскільки розмір однієї зі сторін диванів рівний \(n-1\), то не можна одночасно помістити більше одного горизонтального та більше одного вертикального дивана. Тому потрібно розглянути декілька випадків:
Усі дивани горизонтальні. Для цього випадку потрібно лише перевірити, в яку кількість рядків може поміститись диван.
Усі дивани вертикальні (аналогічно).
Один диван горизонтальний, усі інші — вертикальні. Для цього можна перебрати, куди буде поставлено горизонтальний диван, після чого задача зводиться до попередньої.
Один диван вертикальний, усі інші — горизонтальні (аналогічно).
Знайдемо суму усіх заданих чисел, окрім перших \(min(n, 47)\), та позначимо цю суму як \(s\). Усі інші числа послідовними операціями ділення зведемо до 1. Далі послідовно опрацюємо кожну з одиниць, окрім однієї, наступним чином: знайдемо наймолодший нульовий біт у \(s\), та послідовними операціями множення перетворимо поточну одиницю на цей біт. Таким чином, використовуючи \(min(n, 47)-1\) одиниць, усі нульові біти в \(s\) будуть покриті, отже сума перетвориться на \(2^k-1\). Оскільки одну з \(min(n, 47)\) одиниць ми залишили, загальна сума буде степенем двійки.
Неважко побачити, що потрібна кількість операцій буде значно меншою за \(2 \cdot 10^5\).
D. Злиття послідовності і перестановки
Якщо всі числа в \(a\) однакові, то відповідь -1.
Інакше, знайдемо усі пари сусідніх елементів в \(a\), які є однаковими. Таких пар буде не більше ніж \(n-2\). Це означає, що можна послідовно для кожної із пар знаходити число (серед чисел від 1 до \(n\)), яке ще не було використано і яке не рівне їх значенню. Таке значення знайдеться, оскільки завжди буде хоча б 2 числа, які залишились.
Усі числа які не були вставлені всередину послідовності \(a\) можна розмісити вкінці. Оскільки чисел залишиться хоча б 2, то точно знайдеться одне, яке є іншим ніж останнє число в послідовності.
E. Перестановки в перестановці
Нехай потрібно перемістити значення \(val\) з позиції \(from\) на позицію \(to\) за мінімальну кількість кроків. Спершу припустимо що \(to < from\), тобто число \(val\) необхідно посунути ліворуч на \(from - to\) позицій. Це означає, що треба \(from-to\) разів поміняти елемент \(val\) з елементом котрий знаходиться ліворуч від нього.
Перепишемо умову того що можемо поміняти місцями два сусідні елементи: \(p_{i-1} \le p_i + d\). Виходить, що умовою того що, можна поміняти елемент ліворуч від \(val\) з \(val\) є наступна: \(p_{i-1} \le val + d\), де \(i\) — поточна позиція числа \(val\), а \(i\) — його позиція. З цього випливає, що необхідно вибрати \(from - to\) найближчих до \(val\) елементів перестановки котрі знаходяться ліворуч від \(val\) і сунути кожного з них праворуч, поки не поміняємо їх місцями з \(val\), в порядку справа наліво. Це завжди можна зробити, тому що якщо існує якийсь елемент \(x\), такий що \(x > val + d\), то інший елемент \(y\), такий що знаходиться ліворуч від \(x\) і \(y \le val + d\) завжди можна буде поміняти місцями з \(x\), тому що \(val < x - d\), а \(y \le val + d < x - d + d = x < x + d\).
Тому відповідь буде рівна \(from \cdot (from - to) - \frac{(from - to) \cdot (from - to - 1)}{2} - s\), де \(s\) — це сума індексів \(from-to\) найближчих до \(from\) елементів ліворуч, що не перевищують \(val + d\). Цю суму можна знайти спуском по дереву відрізків, або двійковим пошуком разом з фенвіком, якщо влаштувати скануючу пряму по значеннях елементів.
Випадок \(to > from\) можна розглянути аналогічно. В цьому випадку умовою буде \(p_{i+1} \ge p_i - d\), тому треба буде знаходити найближчі \(to-from\) елементів праворуч від \(from\), які більші або рівні за \(val - d\). Це така сама задача як і попередня, якщо розвернути перестановку і зробити заміну: \(p'_i = n - p_i - 1\).
Розв’яжемо задачу для фіксованого \(c\). Для цього достатньо знайти компоненти зв’язаності по усіх білих вершинах, між якими є шлях із не більше ніж \(c\) чорних. Запустимо BFS одночасно з усіх білих вершин і знайдемо для кожної вершини найменшу відстань до неї \(d_i\) та індекс найближчої білої вершини \(p_i\). Якщо для якогось ребра між \(u\) та \(v\) виконується що \(d_u + d_v \le c\), то об’єднаємо \(p_u\) та \(p_v\) у в одну множину, використовуючи структуру даних "система неперетинних множин". Можна показати, що після такого процесу, усі пари білих вершин, між якими є шлях із не більше ніж \(c\) чорних, будуть об’єднані в одну множину.
Для того, аби відповідати на запити із різними значеннями \(c\), достатньо посортувати їх по \(k_i\), а також посортувати список подій об’єднання за значення \(d_u + d_v\). Перебираючи події, можна рухатись вказівником і виконувати потрібні об’єднання, а після цього відповідати на поточний запит використовуючи СНМ.
G. Найнижчий найвищий спільний предок
Для кожного кольору порахуємо розмір компоненти — кількість вершин, пофарбованих у цей колір. Зауважмо, що таких різних розмірів буде не більше ніж \(\sqrt{2n}\), оскільки їх сума до \(n\).
Знайдемо для кожного розміру LCA (lowest common ancestor) усіх вершин усіх кольорів з компонентами такого розміру. Якщо хоча б одна із цих компонент буде використана у відповіді, то загальне LCA буде не нижче ніж ця вершина, за винятком випадку коли відповідь — це одна компонента, який можна опрацювати окремо. Отже, для кожного розміру знайдемо LCA усіх вершин та кількість компонент такого розміру; самі компоненти стають однаковими.
Зауважмо, що для того, аби знайти LCA для довільного набору компонент, достатньо знати вершину з найменшим та найбільшим часом входження DFS, і LCA між ними буде співпадати із загальним LCA.
Отже, посортуємо усі розміри компонент по часу входження в LCA, і зробимо динамічне програмування зі станом \([size][sum]\), де \(size\) — поточний розмір компонент, \(sum\) — поточна загальна сума розмірів вибраних компонент, а результат — мінімальний час входження DFS по LCA усіх вибраних компонент. При переході нам потрібно перебрати, скільки компонент поточного розміру попадуть у відповідь. Для того, аби ефективно виконати цей перехід, можна окремо опрацювати значення \(sum\) по усіх остачах від ділення на \(size\), і використати алгоритм знаходження мінімуму на черзі для обчислення результату переходу динамічного програмування. Після довільного переходу ми можемо вирішити, що він останній, і оскільки ми знаємо LCA із найменшим часом входу DFS, а поточний \(size\) має LCA є з найбільшим часом входу (оскільки вони посортовані), то LCA між ними і буде кандидатом на відповідь для поточного \(sum\).
Загальна складність: \(O(n\sqrt{n})\)