CHEF-Dynamic Inversion

LINK -https://www.codechef.com/problems/DYNAINV
Problem : Maintain the number of inversions in the permutation (modulo 2), while performing swap operations.


note-- if array do not contain duplicate elements than only this approach will work ..
also -- we cant calculate change in inversion using this method  

0R

You are given a permutation A of the first N positive integers. You are also given Q queries to perform one-by-one, the i-th is defined by a pair X_i Y_i and has the meaning that you swap the X_i-th number in the permutation with the Y_i-th one. After performing each query you should output the number of inversions in the obtained permutation, modulo 2.

The inversion is such a pair (i, j) that i < j and A_i > A_j.

Input

The first line of input contains two space separated integers N and Q - the size of the permutation and the number of queries.

The second line contains N space separated integers - the permutation A.

Then there are Q lines. The i-th line contains two space separated integers - X_i and Y_i, denoting the i-th query.

Output

Output Q lines. Output the number of inversions in the permutation (modulo 2) after performing the first iqueries on the i-th line.

Constraints

• 1 ≤ N ≤ 100, 1 ≤ Q ≤ 100 : 14 points.
• 1 ≤ N ≤ 1000, 1 ≤ Q ≤ 1000 : 23 points.
• 1 ≤ N ≤ 10⁵, 1 ≤ Q ≤ 10⁵ : 63 points.
• 1 ≤ X_i, Y_i ≤ N
• X_i isn't equal to Y_i

Example

Input:
5 1
1 2 3 4 5
2 3

Output:
1

***********************************************EDITORIAL******************************************************************************

If you run your solution at the different own test cases, you will note that no matter which numbers we swap, the parity of the number of inversions will always change (AFTER EACH SWAP IF SWAP IS NOT ON SAME INDEX ). This gives rise for the following solution:

Read the permutation and calculate the number of inversions in it. This can be done in any known way, as it's a standard problem. For example, you can use fenwick tree or merge sort. Writer's solution uses fenwick tree. But this is even an overkill here, because you only need the number of inversions modulo 2. You can use the fact that the permutation 1 2 3 ... N has 0 inversions and every swap operation changes the parity of the number of inversions.
Then, read Q queries. No matter what pair of numbers we swap, the parity of the number of inversions in the permutation will change. So the answers will have zeroes and ones alternating.


But how to prove that the parity will always change?

Let's call transposition a swap of two adjacent numbers in the permutation, namely, swap of ai and ai+1.

Let's show that a single transposition always change the parity of the number of inversions. It's easy to see that if the pair (i, i+1) makes an inversion, then after the transposition this pair will not make an inversion and vice versa.

Now consider a general case: when you swap AL and AR (L < R). Say, we want to place AR to the L-th place. We needR-L transpositions to do it.

After we do them, we obtain:
1 2 ... AR AL AL+1 ... AN



Here AL stands at the position L+1, so we need R-L-1 extra transpositions to put it to the R-th place. Then, we'll get:
1 2 ... AR AL+1 ... AL AR+1 ... AN

But that is exactly what we wanted to obtain - this new permutation is obtained from the initial one by doing just a single swap. Now, let's calculate the total number of transpositions done: (R-L)+(R-L-1). It's equal to 2(R-L)-1 - this number is always odd. So the number of transpositions done in the swap is always odd, and knowing that every transposition changes the number of inversions we obtain that every swap changes the number of inversions as well







***************************************************CODE******************************************************************

#include<iostream>

using namespace std;

 typedef long long int lli;

 #include<bits/stdc++.h>

 lli ic=0;



lli merge (lli arr[],lli start,lli mid,lli end)

   {

   

      lli i=start, j=mid+1;

      lli p=start;

       lli temp[100000];

       lli lc=0;

        while(i<=mid && j<=end)

         {

          

          if(arr[i]>arr[j])

           {

            lc+=mid-i+1;

            temp[p++]=arr[j];

             j++;

     }

     else

     {

      temp[p++]=arr[i++];

     }

          

   }

   while(i<=mid) temp[p++]=arr[i++];

   while(j<=end) temp[p++]=arr[j++];

   for(int i=start;i<p;i++) arr[i]=temp[i];

   return lc;

   }

  

 void  divide(lli arr[],lli start,lli end)

  {

    

   if(start<end)

    {

    

      lli mid=(start+end)/2;

       

     divide(arr,start,mid);

      divide(arr,mid+1,end);

      ic+=merge(arr,start,mid,end);

    }

     



  }

  

 int  main()

  {

   

   

      ic=0;

       lli n;

       cin>>n;

       lli q; 

    cin>>q;

     lli crr[n+10],brr[n+10],arr[n+10];

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

        {

          cin>>arr[i];

          brr[i]=arr[i];

            

     }

     divide(brr,0,n-1);

     int f=ic%2;// INITIAL STATE OF  NO OF INVERSION EVEN OR ODD

     while(q--)

      {

       

         lli a,b;

            cin>>a>>b;

        

       

         

        

        if(a==b)

         {

           cout<<f<<endl;// SINCE TRYING TO DO  SWAP ON SAME INDEX SO NO                                                        //CHANGE  IN STATE (E OR O )OF NO OF INVERSION

            continue;

      }

          cout<<abs(f-1)<<endl;

          f=abs(f-1);// CHANGING STATE OF INVERSION SINCE  SWAP IS DONE

      }

     

  

  return 0;

  }