Бібоп, Рокстеді і операція Шреддера#12987

Бібоп, Рокстеді і операція Шреддера (Editorial)

Розглянемо операцію Шреддера для одного біта:

Тобто, якщо є рівно одна одиниця серед двох значень, то вона переміститься в a_j. Отже, щоб максимізувати суму на відрізку [l,r], потрібно перемістити туди якомога більше одиниць кожного біта. Якщо cny_i — кількість чисел із включеним -им бітом у всьому масиві, то для відрізка відповідь рівна:

\sum_{i=0}^{19} \min(r - l + 1, cnt_i) \cdot 2^i