kabirsahni8's blog

March Easy
By kabirsahni8, history, 8 years ago, In English

Given an array how to find sum of all f(A',k) where A' is subarray of A(original array) and f(A',k) are total unordered pairs (i,j) such that abs(A[i]−A[j])>=k.How to solve this using segment tree.What should be the merge function? Problem link :Problem link

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I don't think you can solve it directly using a segment tree. My approach was:

Find a pair i>j of a[i]-a[j]>=k or a[i]-k>=a[j]. This pair will be counted when r>=i and l<=j or (j+1)*(n-i) times. So the solution looks like this:

  1. Compress the range to 1 until n.

  2. Use a fenwick tree or segment tree to get a range sum query and do something similar to counting the inversions of an array. You are on a[i] and you need to find all a[j] such that a[i]-k>=a[j] and do (j+1)*(n-i). You have n-i, to get the (j+1) you update the tree on the position of a[i] on the compressed range adding (i+1) there. Use binary search (upper_bound — 1) to find the last position where a[i]-k>=a[j] and do ans+=sum_qry(0, last_position)*(n-i). The arrays are 0-based.

  3. Reverse the array and do the same again.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Very helpful!I just didn't understand how update works here.The indices of the sorted array change,how do we tackle that?

    → Reply