Prepared by: Ivan Janjić

Let's look at the definition of an island. It is an interval, thus it is defined by the positions of its left and right border. Maximality ensures that immediately to the left and right is sea or a border of a query. It's not hard to prove that two islands have no borders in common and that every island has exactly two borders. Therefore, to count islands, it's sufficient to count borders and divide the number by ~2~. Let's observe a single query. Let's imagine an interval ~[l, r]~ as a sequence of zeroes and ones, where 1 means relief is higher than the sea level at that position, and 0 otherwise. Add zeroes to the beginning and end of this sequence. Now the task is to count how many times do situations 01 and 10 occur.

To solve the first subtask, it was enough to do exactly what was described above. Overall complexity of this approach is ~\mathcal O(nq)~.

To solve the second subtask, we use the fact that we are given queries in advance and that the mentioned sequence does not change much when going from one interesting sea level to the next interesting sea level with lower value (Interesting sea levels are a set that contains heights of all positions in a relief and all heights encountered in queries). More precisely, some zeros get turned to ones. Turning a 0 to 1 can only affect ~2~ borders. As all queries ask for the number of islands for the whole relief, it was enough to maintain for every boundary between positions whether it is a border of an island or not, update the total amount accordingly and answer a query when sea level is exactly the one requested in the query. Overall complexity of this approach is ~\mathcal O(n+q)~.

To solve the third subtask, it was enough to observe that, given the relief structure, there can be no more than two islands in each query. What's left is to determine the conditions for when there are ~0~, ~1~ or ~2~ islands. Details are left as an exercise to the reader. Overall complexity of this approach is ~\mathcal O(n+q)~.

We use the idea for the solution of the second subtask to solve the full problem. When looking at the sea at some particular level, we need to know how many boundaries are island borders in an arbitrary interval. When changing the sea level, we need to update some boundaries. We need to do the first operation ~q~ times, and the second ~\mathcal O(n)~ times overall, as we will update every position exactly once. These operations can be implemented with a segment tree built on the boundaries between positions. Overall complexity of this approach is ~\mathcal O((n+q) \log n)~.