All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
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 (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 ≤ 105, 1 ≤ Q ≤ 105 : 63 points.
- 1 ≤ Xi, Yi ≤ N
- Xi isn't equal to Yi
Example
Input: 5 1 1 2 3 4 5 2 3 Output: 1
The first hint from this question was the modulo 2 part . This gave a clear understanding that the solution should be trickyand mathematical . The illustration can be done through and example
Suppose we have this array
6 1 2 3 5 2 2 7 6 9 14 30 15 7 .....
Suppose we want to swap the postions 5 and 12 i.e element 5 and 15.
We can make few inferences that elements for elements less than index 5 and greater than 12 we will have no effect on the inversion count as realtive position after the swap remains the same.
Now coming to the elements that lie in between , they can be divided in three categories one that is less than 5 hence less than 15 the other that is greater than 15 and the third the numbers that lie between them both. It is interesting to observe that for elements less than 8 and greater than 15 have no impact on iversion count but only the elements that lie between for example 9 . Now as we can see for every contirbuting element er add an even amount of inversion count. Like for 9, it forms a new inversion with element 15 presently at index 5 and with 8 at index 12. hence we come to this observation that the output is a sequence of ones and zeroes.
Editorialists explanation
Difficulty : SimplePre-requisites : Basic MathProblem : Maintain the number of inversions in the permutation (modulo 2), while performing swap operations.Explanation
At first, let's consider some partial solutions.How to get 14 points
Here you can simulate the whole process. The constraints are designed in such a way that after every swap, you can calculate the number of inversions again by iterating through all the pairs (i, j), where i < j and checking that ai > aj. Then you can output the number of inversions after taking it modulo 2.How to get 37 points
There are faster methods of calculating the number of inversions, for example O(N log N) algorithm using the merge sort. If you have the same idea as in the 14-point solution, but calculate the number of inversions faster, you can haveO(QN log N) solution that will fit in the TL for the second subtask and will bring you additional 23 points.Please note that all these solutions doesn't use the fact that we're required to output the answer modulo 2. But modulo makes the problem much simpler than without modulo version. Though, the version without modulo part can be solved within the same time and memory bounds (see related links) for the given constraints.How to get 100 points
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. 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.
Related links
- A problem at SPOJ where you can check your inversion-finding logic. It requires you nothing but calculate the number of inversions in the array.
- A version of this problem without the modulo part at SPOJ. There you need to use some cleverer logic about maintaining the number of inversions. Pay attention that the given array there is not a permutation, so the parity of the number of inversions will not necessary change after every swap there.
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int bit[200010];
int arr[200010];
int n;
int brr[200010];
void update(int idx,int val)
{
while(idx<=n)
{
bit[idx]+=1;
idx+=idx & (-idx);
}
}
int query(int idx)
{
int sum=0;
while(idx>0)
{
sum+=bit[idx];
idx-=idx & (-idx);
}
return sum;
}
int main()
{
long long int ans=0;
cin>>n;
int q;
cin>>q;
for(int i=0;i<n;i++)
{
cin>>arr[i];
brr[i]=arr[i];
}
/* data compression is used although not necessary*/
sort(brr,brr+n);
for(int i=0;i<n;i++)
{
int sorted=(lower_bound(brr,brr+n,arr[i]))-brr;
arr[i]=sorted+1;
}/* goes like the range update point query part*/
// query of arr[i]-1
//update arr[i] with +1
for(int i=n-1;i>=0;i--)
{
ans+=query(arr[i]-1);
update(arr[i],1);
}
//cout<<ans<<endl;
ans=ans%2;
int a,b;
while(q--)
{
cin>>a>>b;
ans=(ans+1)%2;
cout<<ans<<endl;
}
return 0;
}
