As asked by few people on facebook, I am posting my solution to the problem here
In the question let us assume the permutation of the row as N nodes of a chain connected by N - 1 edges. Let the value of each edge be the maximum of the two elements it is connecting.
Now if we are coloring all the nodes whose values are less than or equal to X, let us assume all the nodes are separate Islands initially. So there are X Islands initially.
Now we connect two adjacent Islands together and make a single Island if the maximum value of the two Islands is less than of equal to X (why?) and the count of number of Islands decreases by one. But the maximum value between two Islands is the value of the edge connecting it. So all those edges whose value is less than or equal to X will decrease the count of number of Islands by one.
We can count the number of edges whose value is less than or equal to X by using Binary Indexed Trees or Segment Trees.
In the update operation if we are swapping two different elements the values of the edges connecting those two elements will change. So we need to update 4 edges twice. Complexity ~ O(8 * Q * log(N)).
4 Likes
The way I approached this problem was a little different.
Lets say we color the nodes in increasing order of their values. So, we will color node 1 first, and the number of island will be 1.
Then we color the node numbered 2. If 2 is adjacent to 1, in the given permutation, the number of island remain the same, ie 1, otherwise it increases by 1. Then we color number with value 3.
If the permutation was (1,3,2), then before coloring 3, we will have 2 islands, but as we color 3, we actually combine 2 existing islands.
Thus each node either increase the number of islands by one, keep it same or decrease the number of island by one if we color the nodes in order. So we can associate one of these 3 values with each node {-1,0,1}. And we can decide this value just by looking at the node number of the node just left and right to it. If node number x, has both its neighbors numbered lower than x, then coloring node x, will merge 2 existing island hence -1(the contribution of node x to the number of islands).
If both its neighbors are greater, then contribution will be +1. else 0.
So we observe that given a permutation, we can directly say, what values each node gets.
Then using a BIT, we can answer the query in O(logN) Finding the sum in BIT, for the first x numbers. Also, while swapping, the values of atmost 6 nodes will be affected. So swap queries can also be answered in O(6*logN).
2 Likes