Зауважимо, що ми можемо скористатися бінарним пошуком по відповіді.
Маючи зафіксовану відстань \(x\), потрібно визначити чи можна розфарбувати дерево у щонайбільше \(k\) кольорів так, щоб максимальна відстань між вершинами одного кольору була не більшою за \(x\).
Скористаємося методом динамічного програмування. Вважатимемо, що дерево є підвішеним за довільну вершину. Нехай \(C_i\) — мінімальна кількість кольорів, необхідна щоб розфарбувати піддерево вершини \(i\). Також, нехай \(D_i\) — мінімальна можлива при цьому відстань від вершини \(i\) до вершини такого ж кольору.
Припустимо, що ми хочемо знайти \(C_a\) та \(D_a\) для вершини \(a\), при тому що нам вже відомі значення \((C_{b_1}, D_{b_1}), (C_{b_2}, D_{b_2}), \dotsc , (C_{b_l}, D_{b_l})\) для усіх синів вершини \(a\). Очевидно, що \(C_a \le C_{b_1} + C_{b_2} + \dotsc + C_{b_l} + 1\), адже ми можемо усі піддерева розфарбувати незалежно, а самій вершині \(a\) присвоїти новий колір. Проте, необхідна кількість кольорів може бути меншою, адже можливо деякі кольори можна об’єднати. Впорядкуємо синів вершини \(а\) за зростанням \(D_{b_i}\). Тепер розглянемо деякий префікс цього впорядкованого масиву. Зрозуміло, що якщо ми можемо об’єднати кольори двох останніх синів на цьому префіксі, то можемо приєднати й кольори усіх попередніх синів, адже глибина найглибшої вершини для них є небільшою. Отже, нам потрібно просто знайти найдовший префікс для якого останніх двох синів можна об’єднати. Нехай це префікс довжини \(k\), тоді \(C_a = \sum C_{b_i} - k + 1, D_a = \max D_{b_i}+1\). Зверніть увагу, що випадок, коли жоден з синів вершини \(a\) не може бути одного кольору з вершиною \(a\) (\(min D_{b_i} + 1 > x\)), треба обробити окремо.
Загальна складність — \(O(n \log^2 n).\)
Навчимося ефективно знаходити значення \(f(s, t)\). Розглянемо \(k\)-й префікс рядка \(s\) — \(s_{1..k}\). Знайдемо усі входження цього префікса у рядок \(t\), нехай \(p\) — позиція довільного входження. Зрозуміло, що \(|lcp(s, t_{p..|t|})| \ge k\) і що в позиції \(p\) будуть розпочинатися входження усіх префіксів \(s\) довжиною від 1 до \(|lcp(s, t_{p..|t|})|\). А тому значення функції \(f(s, t)\) є рівним значенню \(\sum_{i = 1}^{|s|} cnt(s_{1..i}, t)\), де \(cnt(x, y)\) — кількість входжень рядка \(x\) у рядок \(y\).
Ефективний спосіб шукати кількість входжень кожного префікса рядка \(s\) у рядку \(t\) є загальновідомим: побудуємо суфіксний автомат по рядку \(t\). Потрібно для кожної вершини автомату знайти розмір множини позицій закінчення входжень, якій відповідає ця вершина. Це робиться динамічним програмуванням по дереву суфіксних посилань автомата. Ми не будемо детально зупинятися на цьому прийомі в межах цього розбору, адже цю інформацію можна знайти в інтернеті.
Нам достатньо побувати суфіксний автомат для рядка \(t\) всього один раз і використати його для обчислення \(f(s_i, t)\) для усіх рядків з набору. Загальна складність розв’язку є лінійною від суми довжин усіх рядків.
Для початку нам потрібно отримати палку довжини 1. Яку палку для цього є зміст використати? Зрозуміло, що нам є зміст укорочувати для цього найкоротшу палку. Аналогічно, палку довжини 3 є зміст робити з найкоротшої палки, довжини щонайменше 3, яка ще не використана для отримання палки довжини 1. Продовжуючи ці міркування, отримуємо повний розв’язок. Впорядкуємо палки в порядку неспадання довжини. Роблячи один прохід по впорядкованому масиву зліва на право, знайдемо спочатку яку палку ми будемо використовувати, щоб отримати довжину 1, яку щоб 3 і так далі. В якийсь момент ми не зможемо знайти палку, щоб отримати чергову необхідну довжину. Остання довжина, для якої ми успішно знайшли палку і є відповідь на задачу.
Складність — \(O(n \log n)\).
Скористаємося методом динамічного програмування. Нехай \(D_k\) — відповідь на задачу, якщо в нас є лише перші \(k\) чисел. Як, знаючи \(D_1, D_2, \dotsc, D_k\), знайти \(D_{k+1}\)? Переберемо, яке буде останнє невидалене число безпосередньо перед \((k+1)\)-шим. Якщо воно є взаємно простим з останнім, то відповідь не зміниться, а в іншому випадку — зросте на одиницю. Тобто, \(D_{k+1} = \max_{i=1}^k (D_{i} + [gcd(a_{k+1}, a_i) \neq 1])\).
Складність такого розв’язку — \(O(n^2 \log(\max a_i))\) — цього недостатньо.
Ведемо словник \(M\), який підтримуватимемо під час обрахунку значень динамічного програмування. Нехай \(p\) — просте число, тоді \(M_p\) — найбільше з вже обчислених значень \(D_i\), таке що \(a_i\) ділиться на \(p\). Тепер перехід динамічного програмування, можна описати так:
\(D_{k+1} = \max(\max_{p\ is\ prime,\ p | a_{k+1}}(M_p + 1), D_k)\).
Зрозуміло, що кількість простих дільників числа \(a_{k+1}\) є логарифмічного порядку, а тому для знаходження нового значення динамічного програмування нам потрібно розглянути щонайбільше логарифм значень зі словника \(M\). Аналогічно, після знаходження нового значення динамічного програмування, нам потрібно оновити щонайбільше логарифм записів у словнику \(M\). Таким чином, якщо вважати що нам відома факторизація усіх чисел, а звернення до елементів словника відбувається з логарифмічною асимптотикою, то сумарна складність становитиме \(O(n \log^2 (\max a_i))\), що є прийнятним для обмежень задачі.
Єдине, що залишилося зробити — факторизувати усі вхідні числа. Факторизувати можна за \(\sqrt{a_i}\), проте можуть виникнути проблеми з часом роботи алгоритму, тому можна використати таку оптимізацію. Скориставшись решетом Ератосфена знайдемо усі прості числа, менші за \(\sqrt{\max a_i}\). Кількість таких простих чисел, що менші за \(k\) можна оцінити як \(O(\frac{k}{\log k})\). Кожне число вхідних даних будемо ділити на кожне з знайдених простих чисел доки це можливо. Якщо після усіх ділень отримане число не рівне одиниці, то ми знайшли єдиний простий дільник, який є більшим за \(\sqrt{\max a_i}\). Таким чином ми знайдемо факторизацію усіх вхідних чисел зі складністю \(O(n \frac{\sqrt{\max a_i}}{\log \max a_i})\).
У задачі просять порахувати кількість пар чисел на проміжку \([l, r]\), що їхнє "побітове і" рівне нулю.
Нехай \(C(x, y)\) — кількість пар чисел \((a, b)\), таких що \(a \le x,\ b \le y,\ a \mbox{ AND } b = 0\). Згідно з принципом включення-виключення, кількість пар чисел \((a, b)\), що відповідають обмеженням \(l \le a \le r,\ l \le b \le r\) рівна \(C(r, r) - C(l-1, r) - C(r, l-1) + C(l-1, l-1)\). У задачі просять знайти такі пари, що \(a \le b\). Зауважимо, що існує лише одна пара з \(a = b\) — \((0, 0)\). При \(a \ne b\) буде враховано пари \((a, b)\) та \((b, a)\), проте для відповіді нам треба порахувати таку пару лиш раз, тому поділимо кількість таких пар на 2.
Щоб знайти \(C(x, y)\) скористаємося методом динамічного програмування. Будуватимемо два числа одночасно ідучи від старших бітів до молодших. Використаємо принцип динамічного програмування, де будуть три стани — кількість вже розглянутих бітів, чи перше число вже є меншим за \(x\) та чи є друге число вже меншим за \(y\). Додаючи новий біт потрібно враховувати, що ми не можемо поставити одиничний біт в обидва числа одночасно, а також не можемо зробити число більшим за його обмеження. Cкладність — \(O(\log r)\).
Знайдемо усі точки перетину многокутників. Оскільки обмеження достатньо малі, то можна це зробити просто перетнувши кожну пару відрізків.
Назвемо координату \(x\) цікавою, якщо існує принаймні одна вершина многокутника чи точка перетину двох відрізків, що має таку координату по осі абсцис.
Розглянемо незалежно кожну вертикальну смужку між послідовними цікавими координатами. Знайдемо усі ребра многокутників, що проходять через цю смужку й впорядкуємо їх у порядку зростання ординати точки, що належить цьому ребру і має значення абсцис-координати рівне середині смужки, що розглядається. Розглядаючи ребра в такому порядку, ми можемо підтримувати кількість многокутників, що покривають трапецію, яка зараз розглядається. Кожне ребро або збільшує цю кількість на одиницю, або зменшує. Це можна однозначно визначити за орієнтацією ребра, так як усі многокутники задані в порядку обходу проти годинникової стрілки.
Нехай \(s\) — довільний рядок з нулів і одиниць. Нехай \(F(s)\) — масив чисел, такий, що перше його число рівне кількості однакових символів на початку рядка \(s\), друге число — кількості однакових символів в другій групі і так далі. Наприклад, \(F("0001101") = [3, 2, 1, 1]\), а \(F("111") = [3]\).
Аналізуючи описані операції, можна зрозуміти, які умови є необхідними й достатніми, щоб з рядку \(s\) можна було отримати рядок \(t\):
Перші символи рядків мають бути рівними.
Довжини масивів \(F(s)\) та \(F(t)\) мають бути однаковими, адже ми ніяк не можемо змінити кількість груп однакових символів в рядку.
Розміри перших груп обох стрічок мають бути рівними: \(F(s)_1 = F(t)_1\).
Аналогічно, розміри останніх груп мають бути рівними: \(F(s)_{|F(s)|} = F(t)_{|F(t)|}\).
\(F(s)_i \ge F(t)_i\) для всіх \(i\), адже ми не можемо добавляти нових символів.
\(F(s)_i \equiv F(t)_i\ (mod\ 2\)) для \(i=2..|F(s)|-1\), адже обидві операції не змінюють парність розміру кожної групи.
Очевидно, що функції \(F\) і усі необхідні перевірки можна реалізувати з лінійною складністю.
Виконаємо перші \(m\) кроків і будемо перевіряти, чи Зеник не вийшов за межі многокутника і якщо таке відбулося, то ми знайшли відповідь. Нехай \(P_i\) — позиція Зеника після виконаних \(i\) кроків, де \(i = 0..m\). Після \(j = k \cdot m + r\) кроків ми опинимось у точці \(k \cdot \overrightarrow{P_m} + \overrightarrow{P_r}\).
Якщо \(|\overrightarrow{P_m}| = 0\),
Зеник буде циклічно ходити по тих самих точках і відповідь —
-1. У випадку \(|\overrightarrow{P_m}| > 0\), то після
кожних \(m\) ітерацій Зеник буде
зміщуватися на вектор \(\overrightarrow{P_m}\), і, рано чи пізно,
вийде за межі сногокутника.
Розглянемо остачу \(r\) за модулем \(m\) і подивимось на позиції Зеника після ходів з індексами \(k \cdot m + r\). Якщо розглянути збільшення \(k\) від 0 до нескінченності, то спочатку відповідні точки знаходяться всередині многокутника, а після певного моменту — ззовні. Тому можна скористатися двійковим пошуком по \(k\), щоб знайти першу точку з остачею \(r\), яка знаходиться зовні многокутника. Знайдемо всі такі точки для кожної остачі \(r\) від 0 до \(m-1\). Відповідь буде індекс найменшої з них.
Для розв’язку задачі необхідно навчитися швидко перевіряти, чи належить точка многокутнику.
Перевірити, чи точка \(B\) належить опуклому многокутнику, можна за логарифмічну складність:
Знайдемо найлівішу точку многокутника, якщо таких декілька, то найнижчу, назвемо її \(A\).
Інші вершини многокутника будуть посортовані за полярним кутом відносно точки \(A\).
Для заданої точки \(B\) бінарним пошуком за полярним кутом можемо знайти дві сусідні вершини многокутника \(L\) та \(R\), такі що полярний кут точки \(B\) відносно точки \(A\) лежить між полярними кутами \(L\) і \(R\).
Перевіримо, чи точка \(B\) лежить всередині трикутника \(ALR\).
Отож, вибравши мінімальну відповідь серед усіх остач \(r\) ми отримуємо повний розв’язок з асимптотичною складністю \(O(m \log{n} \log({max\_coord}))\).
Цей розв’язок можна оптимізувати, забравши з асимптотики один з логарифмів. Залишаємо це покращення для читачів вправою на домашнє завдання.
I. Дерево мінімальної глибини.
Побудуємо незважений орієнтований граф з \(n\) вершин. Ребро \((a, b)\) існує в графі, якщо виконується хоч одна з двох умов:
\(a\) є батьком вершини \(b\) у початковому дереві.
Серед дозволених операцій є операція \((a, b)\).
Нехай \(D_i\) — найкоротша відстань від вершини 1 до вершини \(i\) у вищеописаному графі. Максимальне з усіх значень \(D_i\) і є відповіддю на задачу. Усі \(D_i\) можна знайти за допомогою пошуку в ширину з лінійною складністю.
Важливо, що кожна операція змінює усі елементи масиву, а не лише елементи на обраному відрізку. Зрозуміло, що нам вигідно на кожному кроці обирати відрізок з найбільшим середнім значенням. Виникають два запитання:
Скільки кроків потрібно зробити?
Легко показати, що максимальний елемент масиву зменшуватиметься щонайменше на половину на кожному кроці (так як ми точно можемо знайти відрізок з середнім як мінімум \(\frac{\max a_i}{2}\)). А тому кількість кроків обмежена логарифмічним порядком.
Як ефективно шукати відрізок з найбільшим середнім значенням?
Покажемо, що оптимальний відрізок має довжину 2 або 3. Розглянемо довільний відрізок довжини не менше 4. Нехай його середнє арифметичне рівне \(x\). Глянемо на середнє арифметичне перших двох елементів цього відрізка. Якщо воно є більшим чи рівним за \(x\), то ми знайшли менший відрізок, довжини два, який має не гірше значення. Якщо ж середнє арифметичне перших двох елементів є строго меншим за \(x\), то середнє арифметичне решти елементів має бути більшим за \(x\). Цей факт легко довести самостійно, а тому ми опустимо деталі в цьому розборі. Таким чином, ми показали що для будь-якого відрізка дожини щонайменше 4, можна знайти коротший відрізок з не меншим середнім значенням. Тому, щоб знайти оптимальний відрізок досить перевірити лише усі відрізки довжини два та три.
.
Сумарна складність розв’язку — \(O(n \log(\max a_i))\).
Нехай \(f(a, b)\) — індекс першого біта (в порядку від старших бітів до молодших), в якому число \(a\) відрізняється від числа \(b\). Вважатимемо, що \(f(a, a) = -1\). Також, нехай \(a[i]\) — це значення \(i\)-го біту числа \(a\) (0 або 1).
Нехай \(C_{l, x, r, y}\) — кількість таких \(i\) від 2 до \(n - 1\), що \(f(a_{i-1}, a_i) = l, f(a_i, a_{i+1}) = r, a_i[l] = x\) та \(a_i[r] = y\) у початковому масиві. Усі такі значення легко обчислити з складністю \(O(n \log \max a_i)\).
Зауважимо, що кількість локальних максимумів до виконання запитів є рівною \(\sum_{i=1}^m \sum_{j=1}^m C_{i, 1, j, 1}\), де \(m\) — кількість бітів у найбільшому числі з вхідних даних.
Після виконання операції xor, номер першого біта в якому
відрізняються сусідні числа не змінюється, а змінюються лише значення
цих бітів. Зокрема, не важко зрозуміти, що якщо ми виконуємо \(xor\ x\) для всіх елементів масиву
початкового масиву, то кількість локальних максимумів становитиме \(\sum_{i=1}^m \sum_{j=1}^m C_{i, x[i] \oplus 1, j,
x[j] \oplus 1}\). Цей факт дає повний розв’язок з складністю
\(O(n \log(\max a_i))\).