Description

Output

Sample Input

5
9
1
0
5
4
3
1
2
3
0

Sample Output

6
0

我的AC状态：	

	哈哈，时间连题目要求的十分之一都没到，我对树状数组还是很满意的。

	我先简单的说下树状数组求逆序数的方法，先逆序数定义：点击打开链接

看完逆序数的定义，首先从定义上看，我们其实可以转换一下，有一个序列An，假设其中第i数它后面有Ci比他小的，那逆序数就等于C=C1+C2+...Ci+...Cn,他其实就等价于假设其中第i个数，他前面有Di个比他大的数，D=D1+D2+...+Di+...+Dn=C。这个很容易理解的，相信大家都可以看懂。

接下来大家可能认为结束了，很显然，没结束，想一下树状数组的结构，如果求一个数前面有多少个比他大的，他得一直从1一直遍历到无穷。想想都可怕，所以我们得再转换一下，我们是否可以先求出前i个数中有多少个不大于第i个数的呢？这个很简单，我们只要遍历1->i，就解决了，那好，总共有i个数，假设在它前面有x个不大于第i数的，那比第i个数的大的自然不就出来了么，不就等于i-x-1吗？

	好了，分析到这里，我想大家都应该明白了，我得申明一下，树状数组不能直接求一个含有小于等于0的数的序列的逆序数，

至于为什么不能有负数，你想想，数组的下标能有负的吗？至于为什么不能有0，那是因为树状数组的有个0陷阱，这个自己百度，不多说了。

	不能直接求，但我们可以间接求啊，至于怎么求，我只简单的说一下，转换坐标轴的原点不就可以了吗！！假设10000>Ai>-10000，我们就可以把Ai+10000，得到20000
  

   
好的，下面是我的代码：

   


   
#include 
     
      
#include 
      
        #define MAX 1001000 int t[MAX]; int lowbit(int x) { return x&(-x) ; } void update(int pos) { while(pos
       
        0) { count += t[pos] ; pos -= lowbit(pos) ; } return count ; } int main() { int n; while(~scanf("%d",&n) && n) { memset(t,0,sizeof(t)) ; long long sum = 0 ; for(int i = 0 ; i < n ; ++i) { int temp ; scanf("%d",&temp) ; int count = query(temp+1) ; //防止树状数组的0陷阱 sum += i-count ; update(temp+1) ; } printf("%I64d\n",sum) ; } return 0 ; }
       
      
     

你看，，，是不是比归并排序求逆序数少很多代码，也更容易理解了！

   
辛辛苦苦码这么多字，，大家多支持一下啦

   
转载请标明出处