Послідовність 2, 4, …, \(2 \cdot n\) задовольняє нашу умову: \(n\) чисел і кожна пара сусідніх чисел має спільний дільник 2, що більше за 1.
B. Вгадай дужкову послідовність
Будемо перебирати позиції зліва направо. Необхідно за одне запитання визначити яку дужку містить пототчна позиція: відкриваючу чи закриваючу. Пам’ятатимемо позиції відкриваючих дужок, які ще не мають відповідної закриваючої дужки. Дамо запит на проміжку від останньої не закритої відкриваючої дужки до поточного символа. Якщо відповідь на таке запитання позитивна, то поточна позиція містить закриваючу дужку, інакше відкриваючу.
Звернемо увагу на формулу площі трикутника в примітках \(\frac{1}{2}|(x_2-x_1) \cdot (y_3-y_1) - (x_3-x_1) \cdot (y_2-y_1)|\). Оскільки усі координати — цілі числа, то найменша можлива площа рівна \(\frac{1}{2}\). Отже, необхідно порахувати кількість точок що задовольняють \(|(x_2-x_1) \cdot (y_3-y_1) - (x_3-x_1) \cdot (y_2-y_1)| = 1\). У найпростішому блоці можна було перебрати усі можливі значення \(x_1, y_1, x_2, y_2, x_3, y_3\). Для того аби уникнути неоднозначності, ми будемо розглядати трикутники в яких \((x_1, y_1) \le (x_2, y_2) \le (x_3, y_3)\), тобто точки посортовані в порядку зростання першої координати, а у випадку рівності в порядку зростання другої координати.
У наступному блоці можна було перебрати значення \((x_2-x_1), (y_3-y_1), (x_3-x_1), (y_2-y_1)\), нехай це будуть значення \(a\), \(b\), \(c\) та \(d\) відповідно. Із того що ми впорядкували точки то отримаємо такі обмеження \(0 \le a \le c\). Якщо \(a = 0\) тоді має виконуватись \(d > 0\), якщо \(a = c\), то \(b > d\).
Із цих значень ми можемо отримати \(x_1 = x_2 - a\) і ми знаємо \(0 \le x_2 \le n\), а отже \(-a \le x_2 - a \le n - a\). В результаті маємо що \(-a \le x_1 \le n - a\). Якщо ми перепишемо аналогічно інші формули, то отримаємо \(max(0, -a, -c) \le x_1 \le min(n, n - a, n - c)\) та \(max(0, -b, -d) \le y_1 \le min(m, m - b, m - d)\).
Для того аби розв’язати задачу на повний бал достатньо було перебрати \(a\), \(b\), \(c\) та визначити \(d\) з рівняння \(|a \cdot b - c \cdot d| = 1\) розглянувши два випадки \(a \cdot b - c \cdot d = 1\) та \(a \cdot b - c \cdot d = -1\).
Перш за все помітимо, що ми можемо переставляти значення в межах одної громади будь-яким чином.
Будемо діяти жадібно. Для будь-якого листка поставимо значення що є найбільшим в його компоненті і видалимо цю вершину, проте пам’ятатимемо що значення в її батька, якщо такий існує, має бути меншим за значення яке зараз поставили. Тепер для деяких вершин будуть обмеження на значення яке в них можна поставити, тому на кожному кроці необхідно шукати найбільше не використане значення в компоненті, що менше за це обмеження.
Помітимо, що така жадібність буде правильною. Припустимо що існує перестановка чисел що задовольняє умову задачі. Тоді якщо ми поміняємо значення поточної вершини із значенням яке ми ставимо в жадібному алгоритмі, тобто значення \(x\) ми поміняємо на значення \(y\), де \(x \le y\). Тоді усі вершини що мали вагу між \(x\) та \(y\) не включно зменшаться (зсунуться на одну позицію до менших), а значення в вершині якій забрали \(y\) буде найбільшим значення серед тих що залишились \(<y\).
Зауважимо, що якщо під час жадібного алгоритму не існуватиме значення
в компоненті яке менше за обмеження вершини, тоді відповідь
NO.
Вершина з найбільшим значенням має бути з’єднана із коренем, отже ребра на шляху від цієї вершини до кореня мають бути вибрані. Скажемо що вершини на цьому шляху вже розглянуті. Тепер виберемо максимум, що не належить цьому шляху, тобто в вершині що ще не розглянута. Нехай \(cnt\) — кількість ребер аби дійти, ребрами вгору, з цієї вершини до розглянутої вершини. Тоді в нас є такі варіанти: взяти всі \(cnt\) ребер або не взяти одне ребро. У другому випадку всі вершини вище такого ребра будуть мати значення рівне максимуму, а ті що нижче будуть мати значення рівне другому максимуму. Тобто у нас є \(cnt + 1\) спосіб як це зробити. Аналогічний процес будемо робити і для інших значень.
Отже, нам необхідно для кожного числа знати значення \(cnt\). Можемо зауважити, що значення \(cnt\) рівне кількості вершин в яких це значення є максимальним в піддереві. Відповідь рівна добутку значень \(cnt + 1\) для усіх значень відмінних від максимального.
Для опрацювання запитів необхідно вміти перераховувати максимум в піддереві, тоді для старих максимумів ми можемо зменшити \(cnt\), а для нових збільшити. Перераховувати максимум в піддереві можна, наприклад пам’ятаючи в кожній вершині множину максимумів в піддеревах синів. Тоді нам необхідно буде видаляти та додавати елементи в множину.