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【】，可以高效的完成下面两个操作：
- 查询，即求前缀和 sumsum，例如：
- sum(8)=tree[8]
- sum(7) = tree[7] + tree[6] + tree[4]
- sum(6) = tree[6] + tree[4]
- 右图中的虚线箭头是计算 sum(7) 的过程。显然，计算的复杂度是 O(logn) 的，这样就达到了快速计算前缀和的目的。
- 维护。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)
