Number of Components
Contest: Good Bye 2019
Difficulty rating: 3300
Tags: data structures

Suppose that we have an array of $$$n$$$ distinct numbers $$$a_1, a_2, \dots, a_n$$$. Let's build a graph on $$$n$$$ vertices as follows: for every pair of vertices $$$i < j$$$ let's connect $$$i$$$ and $$$j$$$ with an edge, if $$$a_i < a_j$$$. Let's define weight of the array to be the number of connected components in this graph. For example, weight of array $$$[1, 4, 2]$$$ is $$$1$$$, weight of array $$$[5, 4, 3]$$$ is $$$3$$$.

You have to perform $$$q$$$ queries of the following form — change the value at some position of the array. After each operation, output the weight of the array. Updates are not independent (the change stays for the future).

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 5 \cdot 10^5$$$) — the size of the array and the number of queries.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — the initial array.

Each of the next $$$q$$$ lines contains two integers $$$pos$$$ and $$$x$$$ ($$$1 \le pos \le n$$$, $$$1 \le x \le 10^6, x \ne a_{pos}$$$). It means that you have to make $$$a_{pos}=x$$$.

It's guaranteed that at every moment of time, all elements of the array are different.

Output format:
After each query, output the weight of the array.

Constraints:
Time limit: 8.0 s
Memory limit: 256.0 MB

Note:
After the first query array looks like $$$[25, 40, 30, 20, 10]$$$, the weight is equal to $$$3$$$.

After the second query array looks like $$$[25, 40, 45, 20, 10]$$$, the weight is still equal to $$$3$$$.

After the third query array looks like $$$[48, 40, 45, 20, 10]$$$, the weight is equal to $$$4$$$.

Example input:
5 3
50 40 30 20 10
1 25
3 45
1 48

Example output:
3
3
4

Editorial:
Firstly, note that all connected components form segments of sequential indexes. Indeed, let numbers $$$i$$$ and $$$j$$$ lie in one component and let's consider $$$i < x < j$$$. Because $$$i$$$ and $$$j$$$ lie in one component, there exists a path, which connects them: $$$v_1 = i, \ldots, v_t = j$$$, such that $$$v_k$$$ and $$$v_{k+1}$$$ are connected with an edge for any $$$k$$$. Then there exists $$$p$$$, such that $$$v_p < x < v_{p+1}$$$.But if $$$a_{v_p} < a_x$$$, then there exists an edge $$$xv_p$$$, otherwise there exists an edge between $$$x$$$ and $$$a_{v_{p+1}}$$$(because $$$a_x < a_{v_p} < a_{v_{p+1}}$$$).
So, because components are non-intersecting segments, there is no edge between $$$[l_1;r_1]$$$ and $$$[l_2;r_2]$$$, $$$l_1 \le r_1 < l_2 \le r_2$$$, iff $$$min_{x \in [l_1;r_1]}(a) > max_{x \in [l_2;r_2]}(a)$$$. That's why number of components is equal to number of $$$i$$$, such that $$$min_{x \in [1;i]}(a) > max_{x \in [i + 1; n]}(a)$$$, increased by $$$1$$$. So, our task is to calculate number of prefix minimums which are strictly greater than corresponding suffix maximums. To do this, let's set $$$a[0] = \infty$$$ and $$$a[n + 1] = 0$$$. After this let's consider some number $$$h$$$ and build new array $$$b$$$, such that $$$b[i] = 1$$$ iff $$$a[i] \ge h$$$. Then if $$$h = min_{x \in [1;i]}(a)$$$ for some suitable $$$i$$$, array $$$b$$$ looks like $$$11\ldots00$$$. On the other hand, if $$$b$$$ looks like $$$11..00$$$ for some $$$h = a[t]$$$, there exists a unique $$$i$$$ for which prefix minimum is greater than suffix maximum. So, we need to calculate number of $$$h$$$ for which array $$$b$$$ looks in a such way. Note, that array looks like this, iff number of adjacent pair of integers $$$b[t] \ne b[t + 1]$$$ is equal to one. Moreover, for any $$$h$$$ this number is at least one. Thus, we just need to maintain $$$f[h]$$$ (number of adjacent non-equal integers in array $$$b$$$) for all $$$h$$$ and calculate number of $$$h$$$ that have $$$f[h]$$$ equal to minimum. It can be done with segment tree, if we note that, if we change one position in array $$$a$$$, value $$$f[h]$$$ can change only because of integers $$$a[i - 1], a[i], a[i + 1]$$$. Then, changing $$$f[h]$$$ is addition of $$$\pm1$$$ on some segments. But we also need to remember, that we should count only values of $$$h$$$, which are equal to some integer in $$$a[]$$$(so if have query $$$pos, x$$$ we need to activate $$$h=x$$$ and deactivate $$$h=a[pos]$$$ in segment tree).
We are sorry for rather strict TL. This was done because with aim to cut off $$$O(n\sqrt{nlog(n)})$$$ solutions(not sure if we succeed), which worked not slower than solutions on Java with set.