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)
# | User | Rating |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 155 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
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)
Name |
---|
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.