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 Xi Yi and has the meaning that you swap the Xi-th number in the permutation with the Yi-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 Ai > Aj.
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 - Xi and Yi, denoting the i-th query.
Output
Output Q lines. Output the number of inversions in the permutation after performing the first i queries on the i-th line.
Input:
5 1
1 2 3 4 5
2 3
Output:
1
input:
6 2
5 10 15 20 25 30
1 2
3 4
output:
1
0
input:
7 3
1 2 3 4 5 6 7
2 4
6 8
1 3
output:
1
0
1
input:
3 2
8 12 14
5 6
7 8
output:
1
0
input:
6 3
2 5 6 7 3 1
22 33
33 66
11 22
output:
1
0
1
Debug the code
def merges(arr,l,r):
if l < r :
mid=(l+r)//2
a=merges(arr,l,mid)
b=merges(arr,mid+1,r)
c=merge(arr,l,mid,r)
return a+b+c
return 0
def merge(arr,l,mid,r):
c=[0 for i in range(r-l+1)]
p=l
q=mid+1
count=0
for i in range(len(c)):
if p >= mid+1 :
c[i] = arr[q]
q+=1
elif q >=r+1 :
c[i]= arr[p]
p+=1
elif arr[p] > arr[q] :
c[i] = arr[q]
q+=1
else:
c[i] = arr[p]
p+=1
for i in range(l,r+1):
arr[i] = c[i-l]
return count
n,q=[int(c) for c in input().split()]
arr=[int(c) for c in input().split()]
findcount=merges(arr,0,n-1)
ans=findcount/2
for i in range(q):
input()
ans=ans^1
print(ans)
Kindly provide the answer using the below link:
Habitate