В цій задачі можна просимулювати процес, описаний в умові, або ж посортувати масив і за один прохід знайти відповідь.
Неважко побачити, що, оскільки розмір однієї зі сторін диванів рівний n−1, то не можна одночасно помістити більше одного горизонтального та більше одного вертикального дивана. Тому потрібно розглянути декілька випадків:
Усі дивани горизонтальні. Для цього випадку потрібно лише перевірити, в яку кількість рядків може поміститись диван.
Усі дивани вертикальні (аналогічно).
Один диван горизонтальний, усі інші — вертикальні. Для цього можна перебрати, куди буде поставлено горизонтальний диван, після чого задача зводиться до попередньої.
Один диван вертикальний, усі інші — горизонтальні (аналогічно).
Знайдемо суму усіх заданих чисел, окрім перших min(n,47), та позначимо цю суму як s. Усі інші числа послідовними операціями ділення зведемо до 1. Далі послідовно опрацюємо кожну з одиниць, окрім однієї, наступним чином: знайдемо наймолодший нульовий біт у s, та послідовними операціями множення перетворимо поточну одиницю на цей біт. Таким чином, використовуючи min(n,47)−1 одиниць, усі нульові біти в s будуть покриті, отже сума перетвориться на 2k−1. Оскільки одну з min(n,47) одиниць ми залишили, загальна сума буде степенем двійки.
Неважко побачити, що потрібна кількість операцій буде значно меншою за 2⋅105.
D. Злиття послідовності і перестановки
Якщо всі числа в a однакові, то відповідь -1.
Інакше, знайдемо усі пари сусідніх елементів в a, які є однаковими. Таких пар буде не більше ніж n−2. Це означає, що можна послідовно для кожної із пар знаходити число (серед чисел від 1 до n), яке ще не було використано і яке не рівне їх значенню. Таке значення знайдеться, оскільки завжди буде хоча б 2 числа, які залишились.
Усі числа які не були вставлені всередину послідовності a можна розмісити вкінці. Оскільки чисел залишиться хоча б 2, то точно знайдеться одне, яке є іншим ніж останнє число в послідовності.
E. Перестановки в перестановці
Нехай потрібно перемістити значення val з позиції from на позицію to за мінімальну кількість кроків. Спершу припустимо що to<from, тобто число val необхідно посунути ліворуч на from−to позицій. Це означає, що треба from−to разів поміняти елемент val з елементом котрий знаходиться ліворуч від нього.
Перепишемо умову того що можемо поміняти місцями два сусідні елементи: pi−1≤pi+d. Виходить, що умовою того що, можна поміняти елемент ліворуч від val з val є наступна: pi−1≤val+d, де i — поточна позиція числа val, а i — його позиція. З цього випливає, що необхідно вибрати from−to найближчих до val елементів перестановки котрі знаходяться ліворуч від val і сунути кожного з них праворуч, поки не поміняємо їх місцями з val, в порядку справа наліво. Це завжди можна зробити, тому що якщо існує якийсь елемент x, такий що x>val+d, то інший елемент y, такий що знаходиться ліворуч від x і y≤val+d завжди можна буде поміняти місцями з x, тому що val<x−d, а y≤val+d<x−d+d=x<x+d.
Тому відповідь буде рівна from⋅(from−to)−(from−to)⋅(from−to−1)2−s, де s — це сума індексів from−to найближчих до from елементів ліворуч, що не перевищують val+d. Цю суму можна знайти спуском по дереву відрізків, або двійковим пошуком разом з фенвіком, якщо влаштувати скануючу пряму по значеннях елементів.
Випадок to>from можна розглянути аналогічно. В цьому випадку умовою буде pi+1≥pi−d, тому треба буде знаходити найближчі to−from елементів праворуч від from, які більші або рівні за val−d. Це така сама задача як і попередня, якщо розвернути перестановку і зробити заміну: p′i=n−pi−1.
Розв’яжемо задачу для фіксованого c. Для цього достатньо знайти компоненти зв’язаності по усіх білих вершинах, між якими є шлях із не більше ніж c чорних. Запустимо BFS одночасно з усіх білих вершин і знайдемо для кожної вершини найменшу відстань до неї di та індекс найближчої білої вершини pi. Якщо для якогось ребра між u та v виконується що du+dv≤c, то об’єднаємо pu та pv у в одну множину, використовуючи структуру даних "система неперетинних множин". Можна показати, що після такого процесу, усі пари білих вершин, між якими є шлях із не більше ніж c чорних, будуть об’єднані в одну множину.
Для того, аби відповідати на запити із різними значеннями c, достатньо посортувати їх по ki, а також посортувати список подій об’єднання за значення du+dv. Перебираючи події, можна рухатись вказівником і виконувати потрібні об’єднання, а після цього відповідати на поточний запит використовуючи СНМ.
G. Найнижчий найвищий спільний предок
Для кожного кольору порахуємо розмір компоненти — кількість вершин, пофарбованих у цей колір. Зауважмо, що таких різних розмірів буде не більше ніж √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√n)