Блог пользователя bensonlzl

Автор bensonlzl, история, 4 года назад, По-английски

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
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Auto comment: topic has been updated by bensonlzl (previous revision, new revision, compare).

»
4 года назад, # |
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)$$$
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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!

»
4 года назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

ngmh pls help me ^^ :| :<