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

Правка en2, от Aveiro_quanyue, 2023-04-20 08:14:06

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. $$$(a[l], a[l+1], ..., a[r])$$$ is a continuous subarray of $$$a$$$ that starts from $$$l$$$ and ends at $$$r$$$ (both inclusive).

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

Теги combinatorics, data structures, inversion count

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Aveiro_quanyue 2023-04-20 08:14:06 114
en1 Английский Aveiro_quanyue 2023-04-20 08:12:43 371 Initial revision (published)