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

Автор madn, история, 7 лет назад, По-английски

I've been recently thinking about this problem:

Given array of n integers and q queries( l, r pairs ). For each query you need to count number of inversions( i, j pairs such that i < j and a[i] > a[j] ) in subarray from l to r. And you have to answer the queries online(you're not given all queries beforehand).

I was able to come up with a solution that i'd describe below, but I'd like to know if it's possible to solve the problem with better complexity.

So, my solution:

1) preprocessing

Let's divide our array into sqrt(n) blocks, each sized sqrt(n), and merge-sort elements inside each, counting number of inversions in it. Then, for each pair of blocks, count number of inversions such that first element lies within first block and second lies within second block. We can do this using binary search, because each block is sorted already. After that, for each sqrt-block-range( [l, r] range such that l is a left border of one block and r is a right border of other block ) we'd find number of inversions in it by summing precalculated values( inversions in each block and inversions in pairs of blocks). There are around n pairs and ranges so we can do all preprocessing in O(n * sqrt(n) * log(n)). We also need to build merge-sort tree on the array for queries.

2) queries

We already know answer for sqrt-block-range that lies within query range. Then we just need to count inversions that include elements outside sqrt-block-range. There no more than 2 * sqrt of such elements, so we can do this with binary search in merge-sort tree in O(sqrt(n) * log^2(n)), or in O(sqrt(n) * log(n)) with partial cascading.

Overall complexity: O((n + q) * sqrt(n) * log(n)) with partial cascading.

So what are your thoughts, can it be solved faster?

P.S. Sorry for my poor English.

  • Проголосовать: нравится
  • +19
  • Проголосовать: не нравится

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

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Edit: I missed something so this was wrong XD.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    It is O(N lg N) for each query, because you merge sorting a segment of array, is not it?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      yeah I had a mistake in my solution, I didn't mean to do it repeatedly for every query, but I definitely missed something. oops :P

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

yes, it can be (with something of classic sqrt-decomp and MO's algo)

1) divide array to blocks of size

2) calculate answers for all segments [L, r] where L — start of block and r — arbitrary index. Similary for all segments [l, R], R — end of the block. It needs two tables with memory.

3) answer on query [l, r]: find L and R such l ≤ L ≤ R ≤ r. preanswer is invs[L][r] + invs[l][R] - invs[L][R]. remains add inversions i, j such l ≤ i < L ≤ R < j ≤ r (on corners). it can be done with two pointers if you have sorted elements on each block.

So, 2) can be done in time (yes i not described it, try to think about dynamic prog) and 3) in per query

  • »
    »
    3 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

    I liked your approach to the problem very much,

    but as for doing step 2 in O(n.sqrt(n)) time, I have been thinking hard about it and I have not figured out how can it be done ??

    normal counting inversions in array using BIT or merge sort requires O (n.logn) so can you please describe how your suggested DP approach works in more detail, or give me some hints to think about it

    Thanks in advance

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

      ok, hint:

      invs[L,r] = invs[L,r-1] + invs[L+D,r] - invs[L+D,r-1] + azaza

      azaza is inversions of a[r] and element from block L

      by two pointers for sorted a and for sorted block you can calculate each azaza in $$$O(nlogn + n \sqrt n)$$$ total

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        Ahhhh, I see

        I think I almost got it now :).

        but just to make sure I got it all correctly, L+D is the First Block that Comes after Block L, azaza is how many element in block L make an inversion with a[r] which lie outside of block L, right ??

        so if we have sorted block L previously as you said, then we can get azaza using upper_bound on Block L in O(log(sqrt(n)) for a little better complexity.

        so the total complexity of the overall preprocessing should be O(n.sqrt(n).log(sqrt(n))), am I right ??

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

          yes, right

          but total must be $$$O(n \sqrt n)$$$

          sort L-th block

          iterate each element in a after L-th block in increasing order

          with second pointer in block you can achive needed count of inversions

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится

            "iterate each element in a after L-th block in increasing order"

            does this means that I have to sort the part of the array after the current L Block for each block while keeping their indices, right??

            so actually we will have one extran.sqrt(n) array for keeping the azaza values too .

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            while searching more about this, I found this solution: https://stackoverflow.com/a/21790297 which is very similar to yours, but the thing is that he said the complexity is O (n.sqrt(n).log(n)).

            which I think is inevitable, even if we use two pointers to calculate azaza, we still have to sort the " after L-th block in increasing order" part of the array, which will add the log(n) to our complexity.

            I have been thinking hard about it since yesterday, but I can't see yet how it can achieved in just O(n.sqrt(n) :(

            Is there a trick which can help you to traverse the a[r]'s in increasing order without resorting them for each Block L ??

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    can step 3 be done in O(sqrt(n))?

    i can't think of it, if anyone used this idea, please help me out