Автор: | Павло Ціцей |
Підготовка завдання: | Павло Ціцей, Олександр Тимкович |
Розбір: | Павло Ціцей |
Твердження:
Якщо ми маємо два однакових запити, ми можемо працювати з ними як з одним запитом. Це пов'язано з операцією побітового XOR. Маємо, що a\oplus a=0 і a\oplus b\oplus a=b. Отже, якщо ми вибираємо дві однакові операції, це еквівалентно вибору жодної з них. У наступних блоках ми будемо вважати, що всі запити унікальні.
Блок : n\le 5:
Оскільки до 5, ми можемо мати до 10 запитів, тому можемо просто спробувати всі підмножини запитів, якщо вони правильні.
Блок : q\le 20:
Ми можемо спробувати всі підмножини запитів. Щоб не проходити масив, ми можемо створити масив , де a_i=b_1\oplus b_2\oplus\dots\oplus b_i і в цьому масиві запит з до еквівалентний зміні лише b_l та b_{r+1}. Отже, ми можемо підрахувати кількість одиниць у масиві і коли ми змінюємо b_i, якщо воно 1, ми зменшуємо це значення на одиницю і змінюємо b_i, інакше ми збільшуємо значення і змінюємо елемент b_i. Щоб підмножина була відповіддю, нам потрібно, щоб після всіх запитів у нас було нуль одиниць.
Блок : q\le 40:
Припустимо, що - це індекс першого елемента в масиві. Нехай r_1, r_2, ..., r_m - це всі запити типу l, r_i у порядку зростання. Тоді, ми використовуємо запит l, r_1 і видаляємо всі інші та додаємо r_1+1, r_i для всіх , де i>1. Таким чином, якщо ми вибираємо запит r_1+1, r_i, це те ж саме, що вибрати l, r_i. Отже, ми можемо просто робити це багато разів, поки не отримаємо масив, заповнений нулями.
Блок : n\le 64:
Давайте замінимо наш початковий масив на масив , як у першому блоці. Зверніть увагу, що його можна представити як двійкове представлення деякого числа , а запити будуть просто XOR двох степенів двійки (2^{r+1}\oplus 2^l). Тоді нам потрібно зробити число рівним 0. Ми можемо спробувати зробити це жадібно. Давайте відсортуємо масив запитів у порядку спадання. Потім ми будемо послідовно створювати новий масив. Ми додаємо найбільший елемент масиву запитів в кінець цього масиву. Для кожного наступного елемента (нехай це буде ), ми проходимо масив, змінюючи на min(x, x\oplus c_i), де - це -й елемент нового масиву. Якщо не нуль, ми додаємо його в кінець масиву. Щоб отримати відповідь, ми намагаємося змінити так, як ми змінили , і нам потрібно зробити його 0.
Блок : Усі \ell_i різні:
Ми можемо використовувати жадібний алгоритм для розв'язання цього. Давайте почнемо з першого входження елемента 1 в масиві. Очевидно, нам потрібно зробити його нульовим, і може бути лише один запит, що починається в цій позиції (нам потрібно взяти той, що починається тут. Інтуїтивно, це тому, що якщо ми змінюємо масив на масив b, ми змінюємо лише 2 елементи, перший і останній). Отже, ми виконуємо цей алгоритм, поки у нас є запити або поки у нас є якісь 1 в масиві.
Блок : a_i = 1 для всіх :
Якщо ми створимо масив , як у другому блоці, він виглядає як , і кожен запит змінює два елементи, які ми можемо виразити як зміну індексу, де елемент знаходиться. Отже, ми можемо виразити це як граф, де ми починаємо з вершини , а кожне ребро змінює вашу позицію (де ребро - це запит). І вам потрібно дістатися до вершини n+1, що можна зробити за допомогою .
Блок : n, ~q~\le ~1000:
Ми створимо масив , як у другому блоці. Тепер давайте створимо граф, де множина вершин - це вершини масиву , а множина ребер - це запити. Зверніть увагу, що деяка кількість запитів може утворити шлях, і якщо ми використовуємо всі запити на шляху, то лише елементи, які зміняться, будуть першим і останнім. Отже, щоб вирішити задачу, ми можемо зафіксувати один елемент, який є , і знайти шлях до будь-якого іншого елемента, який є . Потім беремо всі запити, тобто шлях. Якщо немає іншого елемента, рівного , немає способу зробити масив рівним нулю.
Блок : без додаткових обмежень:
Ми можемо оптимізувати рішення для блоку 7, створивши MST на графі та зробивши LCA на ньому. Таким чином, ми можемо знайти шлях між двома вершинами за .
Також ми можемо спробувати зробити по-іншому. Ми побудуємо граф, як у блоці , і змінимо b_{l_i} на b_{l_i}\oplus 1. Тепер, якщо ми направимо ребро з l_i до r_{i}+1, нам потрібно змінити b_{r_{i}+1} на протилежне і взяти ребро до відповіді. Якщо ми направимо ребро в іншому напрямку, ми змінюємо b_{l_i} на протилежне і не беремо запит. Тепер нам потрібно направити всі ребра так, щоб деякі вершини мали непарний, а інші парний вхідний ступінь (залежно від значення b_i). Для цього нам потрібно знайти дерево DFS і ребра, які не з дерева DFS, направити в будь-якому напрямку. Потім ми можемо жадібно направити всі ребра в дереві, починаючи з листків. Потім просто перевірте, чи всі вершини мають бажаний вхідний ступінь. Рішення працює за .