Count the number of pairs (l, r) such that the inversion number of (a[l], a[l+1], ..., a[r]) is odd.

Revision en1, by Aveiro_quanyue, 2023-04-20 08:12:43

Given an one-indexed array with $$$n$$$ pairwise distinct elements, find the number of pairs $$$(l, r)$$$ ($$$1 \leq l \leq r \leq n$$$) such that the inversion number of $$$(a[l], a[l+1], ..., a[r])$$$ is odd.

For example, $$$a=[3, 2, 1]$$$, the answer is $$$3$$$: $$$(1, 2), (2, 3), (1, 3)$$$.

Tags combinatorics, data structures, inversion count

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Aveiro_quanyue 2023-04-20 08:14:06 114
en1 English Aveiro_quanyue 2023-04-20 08:12:43 371 Initial revision (published)