Фокус Зеника полягає у тому, що в кінці, після виконання вказаних операцій, буде число 47 для будь-якого початкового числа. Отже, задача зводиться до того аби перевірити чи число \(y\) рівне 47. Також можна було просто відтворити операції вказані в умові використовуючи заданий \(x\).
У задачі необхідно максимізувати значення \((a_i + j) - (a_j + i)\). Перегрупувавши доданки в цьому виразі отримаємо \((a_i - i) - (a_j - j)\). Якщо ми позначимо \(b_i = a_i - i\), тоді нам необхідно максимізувати \(b_i - b_j\). Для того аби максимізувати такий вираз нам необхідно вибрати \(b_i\), як максимальне значення в масиві \(b\). А \(b_j\) вибрати як найменше значення. І як відповідь вивести різницю \(b_i - b_j\).
Також зауважимо, що значення \((a_i + j) - (a_j + i)\) буде таке ж якщо в нас індексація масиву починається з нуля або з одиниці.
Для того аби здати перший блок тестів достатньо було перебрати усі підвідрізки які є в даному та порахувати для них суму. Відповідь буде рівна кількості тих у яких сума рівна 0. Складність такого розв’язку \(O(q \cdot n^3)\), оскільки підвідрізків є не більше ніж \(n^2\) і для кожного з них необхідно порахувати суму, що може займати до \(n\) операцій.
Щоб здати задачу на повний бал необхідно навчитись рахувати суму на підвідрізку швидше ніж за \(O(n)\). Наприклад, це можна зробити порахувавши суму чисел на кожному префіксі. Позначимо суму на префіксі довжиною \(i\) значенням \(pref_i\). Тоді сума на відрізку від \(l\) до \(r\) включно буде рівна \(pref_{r} - pref_{l - 1}\). Також суму на на відрізку \([l, r]\) можна перерахувати з суми на відрізку \([l, r - 1]\) додавши значення \(a_r\).
D. Турнірна таблиця обласної олімпіади
Розглянемо перший блок тестів, де є тільки запити на суму. Учасники не міняються місцями і суму нам необхідно порахувати на певному проміжку учасників, тому ми можемо порахувати значення \(pref_i\) — сума номерів перших \(i\) учасників. Відповідно \(pref_0 = 0\). Тоді сума номерів учасників на відрізку від \(l\) до \(r\) включно рівна \(pref_r - pref_{l - 1}\). Тепер нам необхідно навчитись визначати межі \(l\) та \(r\) для запиту. Для цього будемо пам’ятати \(pos_i\) — позиція учасника з номером \(i\). Тоді межі для запиту \(x_i\), \(k_i\) будуть такі: \(l = pos_{x_i} - k_i\) та \(r = pos_{x_i} - 1\).
Для блоку тестів, де немає запитів першого типу, помітимо те, що лише дві людини міняються місцями в одному запиті. А отже ми можемо оновити значення \(pos\) для цих двох учасників. І зауважимо, те що \(pref_i\) змінюється тільки в позиції \(pos_{x_i}\), а отже ми її можемо перерахувати.
Тепер для усієї задачі необхідно помітити, що Зеник не може обігнати більше ніж \(n + q\) учасників. Це тому, що початково перед ним може бути максимум \(n - 1\) учасник, і запит другого типу збільшує це значення максимум на 1. Ми вміємо оновлювати задачу коли учасник обганяє одного перед собою, тобто ми можемо \(x_i\) разів зробити так, що Зеник обганяє одного учаника перед собою. Сумарно він обжене не більше \(n + q\) учасників, тому сумарна складність \(O(n + q)\).
У реалізації винесено у функцію оновлення усіх значень коли учасник \(x\) обганяє одного учасника над собою.
Для того аби розв’язати задачу необхідно помітити, що останнє число ми можемо визначити порахувавши скільки нових інверсій воно створить. Якщо ця кількість \(x\), то це означає що лівіше є \(x\) чисел більших нього, і відповідно \(n - 1 - x\) чисел менших за нього, а отже його значення \(n - x\). Ми визначили останнє число і тепер можемо продовжити даний процес для передостаннього числа і так далі. Проте для наступних чисел ми повинні врахувати те, що деякі числа вже встановленні. Тобто якщо ми знаємо, що в нас на певному префіксі має бути \(y\) чисел менших за поточне, то нам необхідно вибрати \(y + 1\)-ше число, яке ще не встановлене. Це можна зробити за \(O(n)\). Тоді сумарна складність \(O(n^2)\).
Тепер для повної задачі нам потрібно швидко знаходити \(y + 1\)-ше не використане число. Один із варіантів — це встановити в позиції від 1 до \(n\) одиниці, і коли ставимо число, то в його позиції змінюємо 1 на 0. Тепер в нас стоятиме 1 тільки в позиціях чисел, які ще не встановлені. А отже нам потрібно знайти \(y + 1\)-шу 1-цю. Це є стандартна задача розглянута у відео лекції на тему «Дерево відрізків» на YouTube-каналі Algotester, якщо ми будемо шукати максимальний префікс із сумою \(y\). Тоді потрібне нам число знаходитиметься на наступній позиції. Тепер в цій позиції потрібно замінити 1 на 0.
Розглянемо простий дільник \(p\) числа \(n\), нехай \(b\) — степінь \(p\) в факторизації \(n\), тобто найбільше ціле число таке що \(n\) ділиться на \(p^b\). Якщо НСК(\(n-1, n-2, \dots, n-k\)) ділиться на \(n\), то це означає що ділиться і на \(p^b\). Також можна помітити, що для цього має існувати число, серед \(n - 1, n - 2, ..., n - k\), яке ділиться на \(p^b\). Нехай це число \(n - x\). Тоді оскільки \(n\) теж ділиться на \(p^b\) тоді з цього випливає, що і \(x\) ділиться на \(p^b\). А також ми можемо сказати, що \(p^b \le x\), а отже число \(p^b\) є серед чисел 1, 2, ..., \(k\). Отже якщо НСК(\(n - 1, n - 2, ..., n - k\)) ділиться на \(n\) тоді і лише тоді, коли НСК(1, 2, ..., \(k\)) теж буде ділитись на \(n\). Значить нам необхідно порахувати кількість дільників числа НСК(1, 2, ..., \(k\)). Для першого блоку тестів можна було порахувати це число, розглянути усі його дільники \(n\) та порахувати скільки з них більші за \(k\). Зі збільшенням \(k\) це значення буде дуже збільшуватись і такий розв’язок не можна буде використати для всієї задачі.
Для блоку з одним \(k\) можна помітити, що якщо ми зможемо представити НСК(1, 2, ..., \(k\)) у вигляді \(p_1^{b_1} \cdot p_2^{b_2} \cdot ... \cdot p_m^{b_m}\), тоді кількість дільників такого числа рівна \((b_1 + 1) \cdot (b_2 + 1) \cdot ... \cdot (b_m + 1)\). А також можна помітити що усі числа від 1 до \(k\) є дільниками НСК, тому ми можемо від кількості усіх дільників відняти \(k\). У попередньому абзаці ми показали, що НСК може ділитись на якесь \(p^b\) лише тоді коли \(p^b \le k\). А отже нам достатньо для кожного простого числа \(p \le k\) порахувати максимальне \(b\) таке, що \(p^b \le k\) і порахувати добуток \(b + 1\) по модулю.
Щоб розв’язати повністю задачу необхідно зрозуміти що зі збільшенням \(k\) для деяких \(p\) може збільшитись \(b\). Тому будемо опрацювувати запити в посортованому порядку. І посортуємо усі числа вигляду \(p^b\), що не перевищують \(10^7\). Використавши метод двох вказівників. Коли ми переходимо від одного \(k\) до іншого то деякі значення \(b\) зміняться, а отже нам потрібно буде оновити відповідь. Нам потрібно поділити на старе значення \(b\) + 1 і помножити на нове таке значення. Ділення по модулю на число \(x\), яке взяємнопросте з модулем \(M = 998244353\) — це те ж що і операція множення на число \(y\) таке, що \(x \cdot y \mod{M} = 1\). Для простого числа \(mod\) ми знаємо малу теорему Ферма: \(x^{M - 1} \mod{M} = 1\), а отже \(y = x^{M - 2} \mod{M}\) і його можна порахувати швидким піднесенням до степеня. Також оскільки значення \(b\) не більші за 23, то можна було порахувати обернене значення для кожного числа від 1 до 23 і записати це в масив.
При додаванні точки знайдемо найкоротшу відстань від неї до всіх інших наявних точок. Тепер перевіримо чи ця відстань менша ніж була перед тим. Також в нас є запити видалення, тому нам треба пам’ятати відповідь для попередньо доданих точок. Для цього можна використати стек — структуру яка може додавати елемент в кінець, видаляти з кінця і знати останній елемент стеку.
Для повної задачі необхідно зауважити те що точок на відстані не більшій ніж \(r\) від нової точки, де \(r\) — найменша відстань між всіма іншими точками, є небагато, і нам потрібно порахувати відстань тільки до цих кількох точок. Проте шукати точки на відстані не більше \(r\) від даної доволі складно, тому будемо шукати точки що знаходяться в квадраті з довжиною сторони \(2 \cdot r\) з центром в новій точці. Таких точок не може бути більше 9, тому що в кожному квадраті на рисунку не може бути двох точок, бо інакше була б пара точок що має відстань меншу за \(r\). А тому максимум може бути 9 точок.
Отже нам необхідно шукати точки в прямокутнику, вміти додавати і видаляти точки. Це можна робити використавши дерево відрізків, де в кожній вершині дерева відрізків будемо підтримувати множину точок, впорядковану за \(y\), для усіх точок в яких \(x\) покритий проміжком вершини. При операції додавання або видалення нам необхідно оновити значення в \(O(log)\) вершин, а в одній вершині оновлювати множину можемо за \(O(log)\). Тому складність для однієї операції буде \(O(log^2)\).