SORT 公司是一个专门提供排序服务的公司，该公司的宗旨是：“顺序是美丽的”。他们的工作是通过一系列移动，将某些物品按顺序摆好。他们的服务是通过工作量来计算的，即移动物品的次数。所以，在工作前必须先考察工作量，以便向客户提出收费数目。

用户并不需要知道精确的移动次数，实质上，大多数人都是凭感觉来认定这一列物品的混乱程度。根据 SORTSORT 公司的经验，人们一般是根据“逆序对”的数目多少来称呼这一序列的混乱程度。假设将序列中第I件物品的参数定义为 Ai，那么排序就是将 A1,⋯An 从小到大排序。

若 i<j 且 Ai>Aj，则 <i,j>就为一个“逆序对".

SORT 公司请你写一个程序，在尽量短的时间内统计出”逆序对“的数目

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

思路：

暴力解法：

根据定义，我们遍历数组，如果发现当前的数字后面存在比他大的数，则计数器++。代码复杂度o(n^2)

代码

1. c = 0
2. b = input()
3. a = list(map(int,input().split()))
4. for i in range(0,len(a) - 1):
5. for j in range(i + 1,len(a)):
6. if a[i] > a[j]:
7.       c += 1
8. print(c)

树状数组：

有关这道题的树状数组的解法可以先参考这位博主的文章，讲的很详细。大佬的思路

树状数组是一种用来求前缀和的时间复杂度比较低的数据结构，我们可以通过树状数组讲问题”“改变 n次元素值，查询 n 次区间和”的总复杂度降为 O(nlogn)。

右图圆圈中标记有数字的节点，存储的是称为树状数组的tree[],一个结点上的tree[]的值，就是它树下的直连子节点的和，例如：

• tree[1]=a1
• tree[2]=tree[1]+a2
• tree[3]=a3
• tree[4]=tree[2]+tree[3]+a4
• ⋯
• tree[8]=tree[4]+tree[6]+tree[7]+a8

我们利用tree【】，可以高效的完成下面两个操作：

1. 查询，即求前缀和 sumsum，例如：

• sum(8)=tree[8]
• sum(7) = tree[7] + tree[6] + tree[4]
• sum(6) = tree[6] + tree[4]

2. 右图中的虚线箭头是计算 sum(7) 的过程。显然，计算的复杂度是 O(logn) 的，这样就达到了快速计算前缀和的目的。
   
3. 维护。tree[]本身的维护也是高效的。当元素 a 发生改变时，能以 O(logn) 的高效率修改 tree[] 的值。例如更新了a3，那么只需要修改 tree[3]、tree[4]、tree[8]⋯，即修改它和它上面的那些结点：父结点以及父结点的父结点。
   

至于如何找到下一个节点，我们通过下面的lowbit()去寻找

下面我们介绍四个函数

lowbit(x):

找到一个数的二进制的最后一个1，为什么要找最后一个1呢？因为我们观察维护和查询这两个操作时，不难发现：

1.在查询的过程中，是每次去掉二进制的最后的1。例如求 sum(7) = tree[7] + tree[6] + tree[4]，步骤是：

• 7 的二进制是 111，去掉最后的 1，得 110，即 tree[6]；
• 去掉 6 的二进制 110 的最后一个 11，得 100，即 tree[4]；
• 4 的二进制是 100，去掉 1 之后就没有了。

2.在维护的过程中，是每次在二进制的最后的 1 上加 1。例如更新了 a3，需要修改 tree[3]、tree[4]、tree[8]\cdotstree[8]⋯ 等等，步骤是：

• 3 的二进制是 11，在最后的 1 上加上 1 得 100 ，即 44 ，修改 tree[4]；
• 4 的二进制是 100，在最后的 1 上加 1，得 1000，即 8，修改 tree[8]；
• 继续修改 tree[16]、tree[32]⋯ 等等。

而我们的lowbit()就可以通过二进制的位运算找到我们要修改的节点。其原理是利用了负数的补码表示，补码是原码取反加一。我们通过这个函数来定位我们将要修改的值。

update(x,d)：

执行修改元素的功能，修改元素tree[x]=tree[x]+1，实际上在修改数组tree[]，通过lowbit()找到下一个需要改变的树结点。直到x跳出最大值。

sum(x)

求前缀和a[1]+a[2]+a[3]+...+a[x]

discretize(lst):

离散化列表，把原来的数字，用他们的相对大小来替换原来的数值，而他们的顺序仍然不变，不影响逆序对的计算。

具体过程

我们先将树状数组初始化为0，再将输入的序列离散化，例如：

1 1234 23 234 3434 转化为1 4 2 3 5

再把数字看成树状数组的下标。每处理一个数字，树状数组的下标所对应的元素就+1，从后往前总计前缀和就是逆序对的数量，要参考上面的图。

我们从后往前遍历序列的时候，发现当前数x的前缀和sum(lists[i]-1)为几，则说明此时当前数的右边有几个比它小的数，我们就要在最终答案中加上sum(lists[i]-1)，同时维护树状数组，updata(x,1),这里d我们只取1，意思是这个数被包含进了树状数组，在之后的查询中如果当前的序列中的数大于之前找到的数，就说明找到一对逆序对。

代码2

感谢蓝桥杯官网浪川博主大佬的主页

感谢蓝桥杯罗老师的教程

1. N=50010
2. tree=[0] * 50010
3. 
4. def lowbit(x):
5. return x&-x
6. 
7. def update(x,d):
8.     while(x<=N):
9.         tree[x]+=d
10.         x+=lowbit(x)
11. 
12. def sum(x):
13.     ans=0
14.     while x>0:
15.         ans+=tree[x]
16.         x-=lowbit(x)
17. return ans
18. 
19. 
20. def discretize(lst):
21.     new_lists=sorted(lst)
22.     a=[0]
23. for i in range(len(lst)):
24. for j in range(1,len(lst)+1):
25. if new_lists[j-1] == lst[i] and j not in a:
26.           a.append(j)
27. return a
28. 
29. n=int(input())
30. lists=discretize(list(map(int,input().split())))
31. 
32. print(lists)
33. 
34. num=0
35. for i in range(len(lists)-1,0,-1):
36.   update(lists[i],1)
37.   num+=sum(lists[i]-1)
38. 
39. print(num)