### bensonlzl's blog

By bensonlzl, history, 9 months ago,

I am currently working on the following problem:

• Given a permutation $A$ of length $N$, you have $Q$ queries specifying 2 numbers $X$ and $Y$ that swap the elements at indices $X$ and $Y$. After every query, output the number of inversions in the new permutation. All queries must be answered online.

My current solution can process every query in $\log^2$ $N$ per query and $N$ $\log$ $N$ precomputation, by first precomputing the number of inversions in the initial permutation and using a segment tree with a BBST in every node. Each BBST stores all of the elements in the range covered by the segment tree node.

We perform a range query on the value at index $X$ and the value at index $Y$ to determine the number of numbers smaller than either number in the segment between them, and then compute the change in inversions. After that, we update the 2 indices in the segment tree. Each of the $\log$ $N$ nodes takes $\log$ $N$ time to update, which gives an overall complexity of $\log^2$ $N$.

My question is: Is it possible to compute the change in inversions more quickly than $\log^2$ $N$? eg. computing the change in $\log$ $N$ time. I suspect that it is possible with either a modification to the segment tree, or using a completely different data structure all together. Any ideas are welcome :)

• +36

 » 9 months ago, # |   +18 Auto comment: topic has been updated by bensonlzl (previous revision, new revision, compare).
 » 9 months ago, # | ← Rev. 2 →   +16 Assuming the changes revert after each query, then:You don't need to modify any values; you can solve this subproblem of counting greater elements than a given value on some subarray in $O(logN)$. You can reduce them to prefix queries and then solve those with a persistent segment tree: $countGreater(L, R, K) = segTree(R).queryGreater(K) - segTree(L-1).queryGreater(K)$
•  » » 9 months ago, # ^ |   +18 The current problem I'm working on has persistent changes, so this won't work, but I was also thinking about the case where the swaps revert after each query as a side problem. Thanks for the idea!
 » 9 months ago, # |   -28 ngmh pls help me ^^ :| :<
•  » » 9 months ago, # ^ |   -37 no fake wallaby
•  » » » 9 months ago, # ^ | ← Rev. 2 →   -28 u then fake muffin lah, I am the real benson the wallaby
•  » » » » 9 months ago, # ^ |   -29 no benson is wabbit