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

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

I know how solve inverse counting using merge sort and infact solved a modified problem.but I am not able to understand how to solve simple inverse counting using segment tree.I read on various site but was not able to understand,kindly help me with the idea

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

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

Let's loop over the permutation, starting from the end, and maintain the array $$$was$$$ where $$$was[x] = 1$$$ if value $$$x$$$ was already visited, otherwise $$$was[x] = 0$$$. At each step you need to find the number pairs $$$(i,j)$$$ such that $$$ i < j \ \&\& \ p[i] > p[j] $$$ holds. This equals to $$$\sum_{x=1}^{p[i]-1} was[x]$$$. Finally, note that you can use segment tree to maintain the array $$$was$$$ efficiently.