DSA-All-In-One/Inversion_count.cpp at main · Amulya-coder/DSA-All-In-One · GitHub

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
77
78
79
80
81
82
83
84
85
86
87
88
/*
Question 2 find inversion count of array
Input :
N
N elemnts of array
Example :
5
8 4 9 2 8
Output :
5
Large input :
5
100000000 10000 10000000000 10 100000000
Output :
5
*/


#include<bits/stdc++.h>

using namespace std;
const int N=1e5+10;
int bit[N];

//Here x parameter is the value
void update(int i,int x){
    for(;i<=N;i+=(i&(-i))){
        bit[i]+=x;
    }
}

int sum(int i){
    int ans=0;
    for(;i>0;i-=(i&(-i))){
        ans+=bit[i];
    }
    return ans;
}

int main(){

int n;
cin>>n;

int a[n+1];

map<long long,int>mp;

for(int i=1;i<=n;i++){
    cin>>a[i];
    mp[a[i]];
}

//Compression of numbers for a[i]>10^6
int ptr=1;
for(auto &pr:mp){
    pr.second=ptr++;
}

for(int i=1;i<=n;i++){
    a[i]=mp[a[i]];

}

//finding the inversion count

int cnt=1;
for(int i=1;i<=n;i++){
    cnt+=sum(N)-sum(a[i]);
    update(a[i],1);
}


cout<<cnt<<endl;

//This will work for a[i]<=10^5;
// for(int i=1;i<=n;i++){
//     cin>>a[i];
//     update(i,a[i]);
// }
// int cnt=0;
// for(int i=1;i<=n;i++){
//     cnt+=sum(n)-sum(a[i]);
//     update(a[i],1);
// }


}