The problem can be solved using Binary Indexed tree or Fenwick tree.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include <cstdio> #include <queue> #include <vector> #include <cstdlib> #include <cstring> #include <iostream> #include <string> #define SZ 100000+5 #define ll long long using namespace std; int arr[SZ]; ll Left[SZ],Right[SZ],sum[SZ]; int mx; ll Cumulative(int idx) { ll value=0; while(idx>0) { value += sum[idx]; idx -= (idx & (-idx)); } return value; } void update(int idx) { while(idx<=mx) { sum[idx]+=1; idx += (idx & (-idx)); } } int main() { int t,N; ll ans; scanf("%d",&t); while(t--) { scanf("%d",&N); mx=-1; for(int i=1;i<=N;i++) { scanf("%d",&arr[i]); if(mx<arr[i]) mx=arr[i]; } memset(Left,0,sizeof(Left)); memset(Right,0,sizeof(Right)); memset(sum,0,sizeof(sum)); for(int i=1;i<=N;i++) { Left[i]=Cumulative(arr[i]);//finds the number of smaller number than arr[i] to its Left update(arr[i]); } memset(sum,0,sizeof(sum)); for(int i=N;i>=1;i--) { Right[i]=Cumulative(arr[i]); update(arr[i]); //ans += Left[i]*(N-) } ans = 0; for(int i=N;i>=1;i--) { ans += Left[i]*(N-i-Right[i]) + Right[i]*(i-1-Left[i]); } printf("%lld\n",ans); } return 0; } |
To know something More.
From the above source:
|
1 2 3 4 5 6 7 8 9 10 11 |
Let's take the first example - 3, 1, 2. At the beginning the BIT is 0, 0, 0. After inserting 3 the BIT is 0, 0, 1. After inserting 1 the BIT is 1, 0, 1 which gives 1 inversion. After inserting 2, the BIT is 1, 1, 1 which gives again 1 inversion. 1 + 1 = 2 total inversions. Let's take the second example - 2, 3, 8, 6, 1. BIT - 0, 0, 0, 0, 0, 0, 0, 0. Insert 2: BIT - 0, 1, 0, 0, 0, 0, 0, 0. Insert 3: BIT - 0, 1, 1, 0, 0, 0, 0, 0. Insert 8: BIT - 0, 1, 1, 0, 0, 0, 0, 1. Insert 6: +1 inversions BIT - 0, 1, 1, 0, 0, 1, 0, 1. Insert 1: + 4 inversions BIT - 1, 1, 1, 0, 0, 1, 0, 1. P.S. In the examples I haven't included the compression for clarity. |
Sample code implementing the binary indexed tree data structure to find the # of smaller numbers than a number of an array.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include<iostream> using namespace std; int ftree[10000001]={0}; int cum(int idx){ int result=0; while(idx>0){ result=result+ftree[idx]; idx=idx-(idx & -idx); } return result; } void update(int idx,int val){ while(idx<=10000000){ ftree[idx]=ftree[idx]+val; idx=idx+(idx & -idx); } } int main() { int t; cin>>t; for(int w=0;w<t;w++){ int n; cin>>n; int ele; long int count=0; for(int i=0;i<n;i++){ cin>>ele; update(ele,1); count=count+cum(10000000)-cum(ele); } cout<<count<<"\n"; for(int i=1;i<=10000000;i++) ftree[i]=0; } return 0; } |