Aveiro_quanyue's blog

Count the number of pairs (l, r) such that the inversion number of (a[l], a[l+1], ..., a[r]) is odd.
By Aveiro_quanyue, history, 19 months ago, In English

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)$$$.

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

»
19 months ago, # |
  Vote: I like it -9 Vote: I do not like it

What are the constraints for n?

→ Reply
  • »
    »
    19 months ago, # ^ |
    ← Rev. 2   Vote: I like it +22 Vote: I do not like it

    This problem is currently open, no constraints now. It is an exercise of mind. An interval dp $$$dp[l][r] = dp[l+1][r] + dp[l][r-1] - dp[l+1][r-1] + (a_l > a_r)$$$ could achieve $$$O(n^2)$$$ complexity.

    → Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it -26 Vote: I do not like it

https://codeforces.net/blog/entry/54082 With this we can find out the number of inversions in an interval in $$$O(\sqrt n)$$$ If we create a segment tree that stores values ​​such as the number of prefixes and suffixes with an even and odd number of inversions and the number of substrings with an even and odd number of inversions that do not contain the first or last element, then for the given interval we find a solution in $$$O(logn\sqrt n)$$$?

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

can fenwick tree+cdq solve this problem? i think it's nlog^2

update : no, and i can't find any polylog solution.

→ Reply
»
19 months ago, # |
  Vote: I like it -6 Vote: I do not like it

my idea is as follows: let's redefine the problem as follows for each index i from 1 to n calculate the number of prefixes that start at i such that the number of inversions on that prefix is odd. to do so, calculate the answer for index 1 then calc the answer for index 2 from the answer of index 1 and so on.

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I guess (prefix sum + fenwick tree) might work

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it +54 Vote: I do not like it

I'm not sure there is a subquadratic solution for this problem, but here's a quite fast bitset-optimized $$$O(n^2)$$$ solution.

Let's imagine the $$$n \times n$$$ matrix $$$M$$$ where $$$M(i, j)$$$ is $$$1$$$ iff $$$j < i$$$ and $$$v_j > v_i$$$. This matrix is always lower triangular. The problem asks us to count the pairs $$$(l, r)$$$ such that the sum over the submatrix $$$M[l:r, l:r]$$$ is odd.

Note that because $$$M$$$ is lower triangular, we can replace $$$M[l:r, l:r]$$$ with $$$M[:r, l:]$$$. The naive solution now clearly resembles compuing 2D prefix sums on matrix $$$M$$$ to find the answer.

Let's consider $$$l \in [0..64)$$$ and $$$r \in [0..n)$$$. We will compute row_msks[i] as the parity of the row sum $$$M[i, l:]$$$ for every $$$l \in [0..64)$$$ packed in a 64-bit number. We do that by processing all indices $$$i$$$ in reversed sorted order. For $$$i \geq 64$$$, we have to also account for the inversions with $$$64 \leq j < i$$$ when computing row_msks[i], but we can do that too by computing the total number of inversions involving $$$i$$$ and subtracting the number of inversions with $$$j < 64$$$ (variable parity in solution below). With a very careful implementation one such step will be total $$$O(n)$$$ work.

After we do one such step we discard the first $$$64$$$ elements and continue.

Total complexity is $$$O(n^2/64)$$$.

Solution is here (including naive solution and stress test):

Solution

A custom invocation on Codeforces reveals that this solution runs in about 700 ms for $$$n = 10^5$$$.

→ Reply