**Swap Pairing( minimum number of steps in which we can make all number pair together)

Swap Pairing

You are given an array of N values. It is guaranteed that N is even and that each distinct value appears in the array exactly twice.

On this array, you can perform the following operation: choose two adjacent numbers and swap them. Compute the minimum number of operations needed such that each pair of equal numbers will be adjacent.

Standard input

The first line contains a single integer N, the length of the array.

The second line contains the N values of the array.

Standard output

The output should contain a single integer representing the minimum number of operations needed.

Constraints and notes

• 1 ≤ N ≤ 100 000
• The values of the array are between 0 and 109

Task Limits

• Time limit: 500 ms
• Memory limit: 128 MB

Input	Output	Explanation
8 7 3 5 3 7 6 5 6	5	The swaps are as follows: 7 3 5 3 7 6 5 6 7 3 5 7 3 6 5 6 7 3 7 5 3 6 5 6 7 7 3 5 3 6 5 6 7 7 3 3 5 6 5 6 7 7 3 3 5 5 6 6

--------------------------------------------------editorial-------------------------------------------------

first observation in this problem is that for any pair   we can shift any one towards any other , it will always give optimal answer ,,,

start from the first element if we  get  any number whose  first pair not used till now than just  map  its position in the array ,

else if we get any number whose first number  is already used , than add index diff of last  occurance and this number  and increase index of all numbers lies b/w these numbers , 9 since we are shifting second number toward first one soo all numbers in b/w these pair shift by 1 index ) 

we can easily do this update , and query using seg tree, 

but use of BIT in such problem will work fast .....

----------------------------------------------code-----seg tree----------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

int arr[1000000];

int val[1000000];

int seg[10000000];

int lazy[10000000];

void build( int idx,int start,int end)

 {

 

  if(start>end) return ;

  else if(start==end)

   {

    seg[idx]=val[start];

    return ;

  }

  build(2*idx,start,(start+end)/2);

  build(2*idx+1,(start+end)/2+1,end);

 }

void update(int idx,int start,int end,int ups,int upe,int val)

 {

  if(start>end || end<ups || upe<start) return ;

  else if(lazy[idx])

    {

       seg[idx]+= lazy[idx];

       if(start!=end)

       {

        lazy[2*idx]+=lazy[idx];

        lazy[2*idx+1]=lazy[idx];

  }

  lazy[idx]=0;

  }

  

  if(start>=ups && end<= upe)

   {

     seg[idx]+=val;

     if(start!=end)

      {

      lazy[2*idx]+=val;

      lazy[2*idx+1]+=val;

  }

  return ;

}

update(2*idx,(start),(start+end)/2,ups,upe,val);

update(2*idx+1,(start+end)/2+1,end,ups,upe,val);

 }

 int query(int idx,int start,int end,int qs,int qe)

  {

   

   

   if(lazy[idx])

    {

       seg[idx]+= lazy[idx];

       if(start!=end)

       {

        lazy[2*idx]+=lazy[idx];

        lazy[2*idx+1]=lazy[idx];

  }

  lazy[idx]=0;

  }

 

  if(start>end || end<qs || qe<start) return 0;

  

  if(start==end)

   {

     return  seg[idx];

}

int a=query(2*idx,start,(start+end)/2,qs,qe);

int b=query(2*idx+1,(start+end)/2+1,end,qs,qe);

return (a+b);

  

  }

  map<int,int> ma;

int main()

{

int  n;

cin>>n;

 

for(int i=1;i<=n;i++) cin>>arr[i];

 

for(int i=0;i<=n;i++) val[i]=i;

 

build(1,1,n);

lli ans=0;

for(int i=1;i<=n;i++)

 {

  if(ma[arr[i]]==0) ma[arr[i]]=i;

  else

    {

   //  cout<<" i "<<i<<" "<<arr[i]<<endl;

      int last=ma[arr[i]];

   //   cout<<"last is "<<last<<endl;

  int id=query(1,1,n,last,last);

  ans+=i-id-1;

 // cout<<"ns "<<ans<<endl;

  update(1,1,n,id,i,1);

  }

 }

 

cout<<ans<<endl;

}

--------------------------------code--------------------bit-------------------------------------------------

#include<bits/stdc++.h> using namespace std; #define ll long long int ll BIT[100010]; int n; void update (int idx,int val) { while( idx <= n) { BIT[idx] += val ; idx += (idx&-idx) ; } } ll query (int idx) { ll ans = 0 ; while (idx > 0 ) { ans += BIT[idx] ; idx -= (idx&-idx) ; } return ans ; } void rupdate(int i, int j, int v) { update(i, v); update(j + 1, -v); } int a[100010]; map<int,int> lt,rt; int main() { // rupdate(4,6,1); //int q=query(6); // cout<<q<<endl; // int n; cin>>n; ll ans=0; for(int i=1;i<=n;i++) { cin>>a[i]; } for(int i=1;i<=n;i++) { rt[a[i]]=i; } for(int i=n;i>=1;i--) { lt[a[i]]=i; } //cout<<"here "<<endl; for(int i=1;i<=n;i++) { int val=lt[a[i]]; //cout<<"here "<<endl; if(i>val) { // cout<<"insie at "<<i<<" "<<endl; int q=query(val); // cout<<"q "<<q<<endl; int l=val+q; // cout<<"cirtual left "<<l<<endl; int r=rt[a[i]]; ll temp=(r-l)-1; ans+=temp; // cout<<"tmep ans "<<temp<<endl; // cout<<"upd iwth "<<val+1<<" "<<r-1<<endl; rupdate(val+1,r-1,1); // cout<<"range upd done "<<endl; } } cout<<ans<<endl; return 0; }