Galactic Sabotage (Problem G, CS3233 Midterm Contest 2024, 2024)
Time limit: 2 sec
Memory limit: 1024 MB

# Problem Statement
Pichuu has just finished his catching spree in the safari zone and decided to spend the day organising his messy PC, where his Pokemon are stored. A PC has multiple boxes in a row and each box can store an unlimited amount of Pokemon. For simplicity, you can assume that the Pokemon in a box are also arranged in a row. Thus, we can define an ordering on Pokemon in the PC, where Pokemon $A$ is before $B$ if and only if $A$ is in a box that is to the left of the box $B$ is in, or $A$ and $B$ are in the same box and $A$ is to the left of $B$. Currently all of Pichuu’s Pokemon are in a single PC box.

He wishes to arrange them in a very specific order, namely he wishes the arrange them such that the the current $i^{th}$ Pokemon in the PC becomes the $A_i^{th}$ Pokemon in the PC. Following the ordering as mentioned above.

This PC is a new gen PC that the Pokemon Center recently upgraded, with only one available function, AutoSort. Where he can instantly arrange the Pokemon anywhere he wants as long as they remain in the same box. For example, if the Pokemon in 3 boxes are $[5, 2, 6], [1, 3], [7, 4]$, he can use AutoSort to instantly arrange the Pokemon as such $[2, 5, 6], [1], [3, 4, 7]$.  
**Note that each Pokemon must remain in the same box.**

Team Galactic have discovered this and plan on using this opportunity to annoy their enemy. They have hacked the PC and is able to manipulate where Pichuu’s Pokemon are. However, they are limited to only being able to separate the Pokemon into $K \le N$ contiguous segments and distributing the segments into separate boxes while maintaining the relative ordering.

For example, $[5, 2, 6, 1, 3, 7, 4]$ in box 1, can be separated into $[5, 2, 6]$ in box 1, $[1, 3]$ in box 2 and $[7, 4]$ in box 3.

They wish to do this optimally such that the number of boxes the Pokemon are in is as large as possible. (Making Pichuu have to navigate through different boxes)  
However, note that they must ensure Pichuu’s can still sort his Pokemon using the AutoSort function. Since if Pichuu is unable to sort his Pokemon, he will be so angry that he goes to Galactic HQ and destroy their HQ.

For example, if Team Galactic splits $[3, 1, 2, 5, 4, 6]$ into 3 boxes as such:  
$[3, 1, 2], [5, 4], [6]$, Pichuu can still sort his Pokemon using the AutoSort function:  
$[1, 2, 3], [4, 5], [6]$.  
However, if Team Galactic splits $[3, 1, 2, 5, 4, 6]$ into 2 boxes as such:  
$[3, 1], [2, 5, 4, 6]$, Pichuu is not able to sort his Pokemon and will destroy Team Galactic.

Furthermore, Pichuu is very fickle and can change his opinion on his Pokemon, swapping the preferred ordering of two Pokemon. Namely, he can choose two Pokemon currently at position $i$ and $j$ and swap $A_i$ and $A_j$.

# Constraints

- $1 \le N, M \le 5 \times 10^5$
- $1 \le A_i \le N$
- $A_1, \dots, A_N$ is a permutation.
- $1 \le U_i, V_i \le N$

# Input

The first line contains a two space-separated integers, $N$, the number of Pokemon and $M$ the number of swaps  
The second line contains $N$ space-separated integers, $A_1, A_2, \dots, A_N$, where $A_i$ represents the position Pichuu wants the Pokemon to be at.  
$M$ lines follows, the $i^{th}$ line contains 2 space-separated integers, $U_i, V_i$ which means that Pichuu swaps the position currently at position $U_i$ and $V_i$.

# Output

Output $M + 1$ lines, each containing a single integer.  
The first integer represents the answer prior to any swaps, and for $2 \le i \le M + 1$, the $i^{th}$ integer represents the answer after the $(i - 1)^{th}$ swap.

# Sample Input #1
```
6 5
3 1 2 5 4 6 
2 3
1 3
3 5
1 2
3 6
```
# Sample Output #1
```
3
3
5
4
3
2
```
# Sample Input #2
```
10 8
1 4 3 2 5 6 7 10 9 8 
8 10
4 2
6 7
6 7
2 4
9 10
4 2
8 9
```
# Sample Output #2
```
6
8
10
9
10
8
7
9
8
```

Sample inputs:
6 5
3 1 2 5 4 6 
2 3
1 3
3 5
1 2
3 6

10 8
1 4 3 2 5 6 7 10 9 8 
8 10
4 2
6 7
6 7
2 4
9 10
4 2
8 9

Sample outputs:
3
3
5
4
3
2

6
8
10
9
10
8
7
9
8

# Solution Analysis

Let’s first try to solve the problem without updates.

Let $R_i$ denote the endpoint of the $i^{th}$ contiguous segment. The array is then split up in to the following segments: $[1, R_1], [R_1 + 1, R_2], \ldots, [R_{K-1} + 1, R_K]$.

In this question we want to maximise $K$, while ensuring that sorting all the individual segments will sort the overall sequence. We call such a partition of the sequence a valid sequence.

**Observation 1**: A sequence is valid if and only if $[1, R_i]$ is a permutation of $1$ to $R_i$ for all $i$.

**Proof**:

- Assume partition is valid, then the first $R_i$ values of the sorted sequence is $1$ to $R_i$. However, as only the elements in the segments are sorted and the segments are not rearranged, the first $R_i$ elements in the final sequence is also the elements in $[1, R_1], \ldots, [R_{i-1} + 1, R_i]$. Thus, $[1, R_i]$ contains $1$ to $R_i$.

- Assume $[1, R_i]$ is a permutation of $1$ to $R_i$ for all $i$. Then $[R_{i-1} + 1, R_i]$ contains the elements from $R_{i-1} + 1$ to $R_i$. Sorting all of the segments individually, we get the sorted sequence of $1$ to $R_1$, sorted sequence of $R_1 + 1$ to $R_2$, etc. Thus merging them we get a permutation.

Let’s define an index $X$ as a valid index if $[1, X]$ is a permutation of $1$ to $X$.

Thus, to maximise $K$, we can find all valid indices and let then be an endpoint of a contiguous segment. And from Observation 1 we know this will be a valid partition. Thus, the maximum $K$ is equivalent to the number of valid indices. This can be calculated in $\mathcal{O}(n)$ with a for loop by keeping track of the running maximum elements. However, we need a faster way of calculating this to accommodate updates.

**Observation 2**: that $X$ is valid index if and only if number of $A_i > X$ in $[1, X]$ is 0.

Let this value be $V_X$ for index $X$. Note that if $X$ is not valid, then $V_X > 1$. Thus if we can maintain a set of values $\{V_1, V_2, \ldots, V_N\}$. Then our answer would be the number of $V_i = 0$. Since 0 would be the minimum number in the set. This resolves to a classic "count number of minimum element" in a segment tree.

To update our values of $V_i$, we can identify how the different values of $A_i$ affect the values of $V_i$.

- **Case 1**: $A_i \le i$  
  Has no impact on any $V_j$ since its only present in $[1, j]$ where $i \le j$. And since $A_i \le i \le j$, it will not be counted in $V_j$. Thus we can ignore this element.

- **Case 2**: $A_i > i$  
  Will be counted in $V_j$ for $i \le j \le A_i - 1$ since this is the only range where it is in the segment and $A_i > j$. This will attribute a range addition of $+1$ to the range $[i, A_i - 1]$.

Hence, we can maintain these updates on the segment tree and whenever there is a swap operation, undo the current updates of the two elements and add the new updates after the swap. The answer can then be obtained from just querying the segment tree.

Note that the initial building of the segment tree involves $\mathcal{O}(n)$ queries and each swap takes $\mathcal{O}(1)$ queries.  
Thus we get a final complexity of $\mathcal{O}(n \log n)$.

Special judge (C++ scorer):