-synx-'s blog

By -synx-, history, 5 years ago, In English
a = 0
while max(V) > 0:
    C = [ 0 ] * max(V)
    for x in V:
        if x%2==0:
            a += C[x//2]
        else:
            C[x//2] += 1
    V = [ x//2 for x in V ]
print(a)
 
 
 
 
  • Vote: I like it
  • +10
  • Vote: I do not like it

»
5 years ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

Consider 2 numbers and . Write them down in binary (Assume both of them to be digit binary number (Incase their length is unequal , pad leading zeroes to the shorter one).



Let be the minimum index such that

So is an inversion pair if and only if index of index of and
So for any , and and and after that they are both equal so each pair gets counted towards as an inversion exactly once.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Suppose
    a = 0000
    b = 1101
    what will l be according to your definition?

    UPD: Got it, the l - 1 subscript must be a typo.