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

doubt in problem 1677A-Tokitsukaze and Strange Inequality and unable to understand from editorial
Автор BLUmOOn, история, 3 месяца назад, По-английски

kindly help in problem 1677A - Tokitsukaze and Strange Inequality,i dont want to use data structure like fenwick tree.I tried to understand it from editorial but am unable to.

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

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

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

→ Ответить
»
3 месяца назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Fix indices a and c such that $$$p_a<p_c$$$ as given in the condition. Then count the number of inversions in the range [a+1,n]. This can be precomputed for all values of a in $$$O(N^2)$$$ or can also be calculated individually for each a as you traverse using an ordered_set or segment tree in $$$O(NlogN)$$$ for each a, resulting in a total of $$$O(N^2logN)$$$. Even though, I doubt that the second approach will pass the given constraints or might just barely manage to escape TLE.

Let the number of inversions in range [i,j] be denoted by $$$Inv(i,j)$$$. Even without precomputation Inv(i,j) can be calculated in $$$O(NlogN)$$$ as mentioned above.

Now, for each index a, the Inv(a+1,n) will contain pair such that both b and d lie in range [a+1,c] or both lie in range [c,n]. Since we want to avoid those cases as it violates the condition $$$a<b<c<d$$$, we subtract $$$Inv(a+1,c)$$$ and $$$Inv(c,n)$$$ from $$$Inv(a+1,n)$$$.

Hence the final answer will be

$$$ \displaystyle \sum_{a=1}^{n-3}\sum_{c=a+2}^{n-1} Inv(a+1,n)-Inv(a+1,c)-Inv(c,n) [p_a<p_c]$$$
→ Ответить
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    thanks for the reply,what are u defining inv(i,j) to be?Won't subtracting inv(a+1,c) mean we are subtracting some pairs of (b,d) that would instead should have been counted.

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

      No, if we count pairs of inversions in the range [a+1,c] that would just mean we are counting all those pairs of {b,d} which satisfy $$$b<d$$$ and $$$p_b>p_d$$$ and lie in range [a+1,c]. But this means that, $$$a<b<d<=c$$$, which violates the condition on indices.

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

        what is inv(i,j),please define it

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

          inv[i,j] = count of all pairs x, y in the range i, j st x < y and a[x] > a[y].

          we are fixing one of the conditions iteratively (a and c) now we only need to handle b, d. we actually need inversions in st one the element of the pair lies inside the range of a and c and the other one lies beyond c. We can calc it as he clearly explained the his first commen. You only need to precompute the inversions in range. As for the preconputation you can follow a strategy of picking an inverted pair i, j and using a 2d difference array to update all the subarrays where both of these indices come. You initialise the difference array such that the prefix sum of it will add 1 to the region where its row <= i and column >= j. At the end prefix sum the entire difference array to obtain your precalculation of inversions in n^2

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

            can u please elaborate on how u calculated inv(x,y),rest all i have understood.how can i precompute no. of pairs {x,y} in range[i,j] st x<y and a[x]>a[y]

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

              I have explained exactly that in my comment above, anyway here 280160949 is an implementation of the problem, study the part where I use difference arrays to calculate the inversions in range.

              You might wanna familiarise yourself with 2D prefix sums.

              → Ответить