Inversions

There are N integers (1<=N<=65537) A1, A2,.. AN (0<=Ai<=10^9). You need to find amount of such pairs (i, j) that 1<=i<j<=N and A[i]>A[j].
 

Input

The first line of the input contains the number N. The second line contains N numbers A1...AN.
 

Output

Write amount of such pairs.
 

Sample Input

Sample test(s)
Input
 
 
5
2 3 1 5 4
 
 
Output
 
 
3
  1. #include"iostream"
  2. #include"algorithm"
  3. #include"cstring"
  4. #include"cstdio"
  5. using namespace std;
  6. #define max 65550
  7. structab
  8. {
  9. int value;
  10. int index;
  11. }a[max];
  12. /*bool cmp(const ab &a,const ab &b)
  13. {
  14. if(a.value!=b.value)
  15. return a.value<b.value;
  16. else
  17. return a.index<b.index;
  18. }*/
  19. bool cmp(const ab&a,const ab&b)
  20. {
  21. return a.value<b.value;
  22. }
  23. int c[max],b[max];
  24. int n;
  25. int lowbit(int x)
  26. {
  27. return x&(-x);
  28. }
  29. void updata(int x,int d)
  30. {
  31. while(x<=n)
  32. {
  33. c[x]+=d;
  34. x+=lowbit(x);
  35. }
  36. }
  37. int getsum(int x)
  38. {
  39. int res=0;
  40. while(x>0)
  41. {
  42. res+=c[x];
  43. x-=lowbit(x);
  44. }
  45. return res;
  46. }
  47. int main()
  48. {
  49. int i;
  50. scanf("%d",&n);
  51. for(i=1;i<=n;i++)
  52. {
  53. scanf("%d",&a[i].value);
  54. a[i].index=i;
  55. }
  56. sort(a+1,a+1+n,cmp);
  57. b[a[1].index]=1;
  58. memset(c,0,sizeof(c));
  59. //memset(b,0,sizeof(b));
  60. for(i=2;i<=n;i++)
  61. {
  62. if(a[i].value!=a[i-1].value)
  63. b[a[i].index]=i;
  64. else
  65. b[a[i].index]=b[a[i-1].index];
  66. }
  67. long long int sum=0;
  68. for(i=1;i<=n;i++)
  69. {
  70. updata(b[i],1);
  71. sum+=getsum(n)-getsum(b[i]);
  72. }
  73. printf("%lld\n",sum);
  74. return 0;
  75. }
上一篇:CEF3开发者系列之外篇——IE中JS与C++交互


下一篇:SQL Fundamentals || 多表查询(内连接,外连接(LEFT|RIGHT|FULL OUTER JOIN),自身关联,ON,USING,集合运算UNION)