ironsoul's blog

By ironsoul, 7 years ago, In Russian

Дана последовательность из N чисел, где N <= 1e5.

Нужно найти сумму всех a[i] xor a[j], что i < j и a[i] > a[j].

Я так понял эта задача решается деревом Фенвика, но как искать не количество инверсий, а их сумму?

Есть ли у операции xor такое свойство?

(a xor b) + (a xor c) = a xor (b + c)

Спасибо

  • Vote: I like it
  • +17
  • Vote: I do not like it