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

Автор striker_46, история, 9 месяцев назад, По-английски

How to find number of elements greater than that elements for all elements of the array on the right side.

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

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

You can use policy based data structure ( Ordered set ) . Then you can traverse the array from the right and keep checking no. of elements using order_of_key(a[i]) . o(nlogn) tc

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

    I guess ordered set not work in case of duplicate element.

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

      It works

      4 types of modification you can do Greater Greater Equal Less Less Equal

      typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
                  tree_order_statistics_node_update>
          op_set;
      
      It acts like ordered-multiset , if you remove equal it acts like normal set
      
»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Also ig it can be done using Divide and conquer ( Merge sort )

Here similar problem on leetcode :

https://leetcode.com/problems/count-of-smaller-numbers-after-self/description/

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

You can also use Segment Tree, if array value is large in that case you have to normalize it down to <=n range.

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

you can sort the array in decreasing order keeping their index then you build segment / fenwick tree ans for index i is i — sum(0..j) j denotes index of element in original array then update the value of segment / fenwick tree. sum(0..i) denotes cnt of elements having value less <= element at index i and index < j

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

Caculate i < j and a_i < a_j. Enumerate from n to 1. For position i, you only need to caculate how many greater than a_i. Use BIT, query(n) — query(a[i]) is answer for position i.

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

    Also, you should normalize a[i] to the range [1,n]

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

    Can you please explain this in a bit more detail and with clarity? Also what is the time complexity of this approach?

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

i guess find the next greater element for every element to its right and add 1 to the answer* of that element to get the answer for this element.

  • answer means-- number of elements to its right such that they are greater than this element
»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I guess you are trying to find count of inversions in array which is

if i < j and a[i] > a[j]

This can be done using merge sort along with a simple modification.

Link to understand sol

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

Statement's really unclear, can you clarify what the problem is?