radal's blog

By radal, history, 6 weeks ago, In English

Hi I faced a problem and I'll be glad if you help me. We have two arrays a and b we want to calculate number of pairs (i,j) such that:

i < j

a[i] > b[j]

 
 
 
 
  • Vote: I like it
  • +10
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
6 weeks ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

You can easily find the solution on stackoverflow

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

For each a[i] can't you just count the number of elements in b to its right that are smaller than it? This is the same as counting inversions in a single array.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you guys, it was really helpful.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

If the values of array are upto 10^9 then we first compress all values in range [1, 1e6] (whatever the size of array) because we are not actually interested in values themselves but the comparison between them. Then use fenwik tree to maintain count of each element upto every index, then anytime if we want number of values less than particular value for example X then we can simply write query(1, X — 1). You can also try a similar question https://codeforces.com/problemset/problem/459/D