UJGOI Таблиця результатів#410

UJGOI Таблиця результатів (Розбір)

Автор:

Павло Ціцей

Підготовка задачі:

Павло Ціцей

Розбір:

Павло Ціцей

Блок : a_i непарне для всіх , n\le 1000: Давайте зробимо префіксну суму масиву, щоб ми могли знайти суму будь-якого підмасиву за , а потім пройти через всі дійсні інтервали. g_{odd} цього інтервалу не дорівнює нулю, якщо кількість непарних елементів непарна, тобто довжина інтервалу непарна. Отже, ми можемо просто перевірити для кожного інтервалу, чи довжина непарна, і якщо так, додати його суму до відповіді.

Блок : n\le 1000: Тут нам потрібно створити два додаткові масиви. Нехай це буде масив і , де odd_i=1, якщо a_i непарне, а в іншому випадку 0. Для масиву , even_i=1, якщо a_i парне, а в іншому випадку 0. Ми можемо зробити префіксну суму на цьому масиві, а потім нам потрібно додати g_{odd}(l,r) для деякого дійсного інтервалу , якщо кількість , для яких odd_i дорівнює 1 (тобто сума елементів на підмасиві масиву ) непарна, що можна обчислити за допомогою префіксної суми. Те ж саме стосується парних, тому ми можемо просто пройти через всі інтервали.

Блок : a_i непарне для всіх : Давайте зафіксуємо якийсь елемент і підрахуємо, скільки разів він включається в суму на інтервалі. Як було зазначено, a_i включається в g_{odd}, якщо кількість непарних елементів на інтервалі непарна, тобто якщо довжина інтервалу непарна, що означає, що і мають різну парність. Отже, ми можемо знайти це, просто підрахувавши кількість в діапазоні від до , які є непарними і парними, і те ж саме для , але в діапазоні від до .

Блок : без додаткових обмежень: Давайте узагальнимо рішення для третього блоку. Отже, якщо елемент непарний, нам потрібно підрахувати кількість інтервалів, де цей елемент включений в g_{odd}, в іншому випадку в g_{even}. Ми припустимо, що завжди включаємо його в g_{odd}, оскільки для g_{even} це симетрично. Отже, для елемента він включений в g_{odd}(l, r), якщо a_i непарне, а інтервал від до має непарну кількість елементів. Давайте створимо масив , як у другому блоці, але з ідеєю з третього. Отже, ми фіксуємо деяке і нам потрібно, щоб парність odd_r відрізнялася від парності odd_l. Для цього ми можемо створити два нові масиви і , де ми підрахуємо кількість парних елементів масиву на префіксі довжини і кількість непарних таких елементів відповідно. Тепер ми можемо підрахувати кількість odd_r, які є парними або непарними, використовуючи префіксну суму на масиві або , і те ж саме для .