Endangered Safari Zone (Problem E, CS3233 Midterm Contest 2024, 2024)
Time limit: 2 sec
Memory limit: 1024 MB

# Problem Statement
Pichuu has just entered the Safari Zone and is amazed by all the rare Pokemon in the Safari Zone. The Safari Zone can be divided into different zones labelled 1 to $N$ arranged in a line from left to right. Using the binoculars from the viewing platform, Pichuu was able to scout all the different zones and notice that there is exactly one pokemon in each zone of species $P_i$ (These Pokemon may be highly territorial).

Since, time in the Safari Zone is limited, Pichuu is planning different routes before entering the area. Each route consist of Pichuu taking the tram to Zone $A$ and walking right till Zone $B$ and then taking the tram back to the entrance. Due to Pichuu’s severe "Gotta Catch Em All" syndrome, he must and will catch any Pokemon on his route (He is a very good catcher), inclusive of the zone he starts and end in.

However, as the Pokemon in the Safari Zone are endangered, if Pichuu catches more than $K$ of same species of Pokemon after he finishes his route, the Pokemon Ranger will confiscate all of Pichuu’s Pokemon of that species. He wishes to catch as many different species of Pokemon as possible to add to his team. Thus, he needs to calculate the number of different species that can be obtained in each of his routes.

However, while planning routes, he may occasionally use the binoculars again to check a zone $A$, and realise that the Pokemon in a zone has changed to species $B$ (Maybe the original Pokemon lost the territory battle). Thus, all of his future plans need to take into account this change when calculating number of different species that can be obtained.

Pichuu is bad at counting and still has to use the Poketch Counter function to count, please help him instead!

# Constraints

- $1 \le N, M, K \le 10^5$
- $1 \le P_i, A_i, B_i \le N$
- $1 \le Q_i \le 2$
- If $Q_i = 2$, then $A_i \le B_i$

# Input

The first line contains three integers, $N, M, K$, which are the number of zones, total number of plans and changes in Pokemon, limit of number of Pokemon of the same species that can be caught without being confiscated.

The second line contains $N$ integers, $P_i$ which is the original species of the Pokemon in zone $i$.

$M$ lines then follow each with three integers: $Q_i, A_i, B_i$
- If $Q_i = 1$, then the Pokemon in zone $A_i$ changes to species $B_i$
- If $Q_i = 2$, then Pichuu is planning a route from zone $A_i$ to $B_i$

# Output

For each query with $Q_i = 2$, output a single integer representing the number of different species that can be obtained from the route.

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

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

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

Sample outputs:
1
3
3

3
1
1
2
2
2

# Solution Analysis

### No Updates

First let us consider how we can solve the question without any updates.

Let’s assume we are currently trying to answer query $[L, R]$. We can ignore the elements after $R$ and only consider elements in $[1, R]$.

Main Idea: For each distinct element, we want to $+1$ but if the number of distinct elements is $> K$ then $-1$.  
Thus, we can $+1$ at the last location of each value and $-1$ at the $(K+1)^{th}$ last location of each value.  Thus querying the range sum of $[L, R]$ would get our answer.

However, if we extend this idea to all queries, we notice that the last and $(K + 1)^{th}$ last location of each value differ based on the value of $R$. We need to be able to update this easily.

Since the queries are all given to us offline. We can sort the queries in increasing $R$ and incrementally add an element to the back to increase $R$. If we precompute for each element where is the next element with the same value, as well as keep track of the current location of the $+1$ and $-1$ for each value. The location of the $+1$ and $-1$ can be very easily updated.

Thus, to answer all the queries we can simply use a fenwick tree or segment tree to update the locations of the $+1$ and $-1$ and when we reach $[1, R]$ we can answer queries that endpoint is $R$ with a range query on the fenwick/segment tree on range $[L, R]$. Thus in total this takes $\mathcal{O}((Q + N) \log N)$

### Small Number of Updates

Now to handle updates, let’s first assume there are very little updates, $\mathcal{O}(H)$, we can consider handling the updates individually. Firstly, let’s define the original array values as $a_i$. And the $t_i$ be the index of the $i^{th}$ update in the original list of updates and queries. (Note that $t_{i+1}$ may be $\ne t_i + 1$ as there may be an query in between the updates) Finally, let $v_i$ and $p_i$ be the new value and location of change for an update.

For every position of the array, we position a index as mutable if there ever exist a update at that position and not mutable otherwise. For each mutable position $x$, let the indices of update that affects this position be $\{u_0, u_1, \ldots, u_k\}$. We will attempt to count the occurrences of values in these mutable positions.

We can then remove the value $a_{p_i}$ from the array and construct a history of values of the position. Constructing a list of $\{(x, a_x, 0, t_{u_0} - 1), (x, v_{u_0}, t_{u_0}, t_{u_1} - 1), \ldots, (x, v_{u_k}, t_{u_k}, \infty)\}$. This represents the (location, value, start time, end time). For each query $[L, R]$ with index $i$, we can then iterate through a combined list of these history of changes and for those with $t_{start} \le i \le t_{end}$ and $L \le x \le R$, we can add 1 to that value in a frequency table. Hence, we have a frequency table of elements in mutable positions in our query range. And if an element appears at least 1 and at most $K$, we can +1 to our sum. This takes $\mathcal{O}(H)$ per query as we are effectively iterating through all queries.

To handle non-mutable positions, we can use the same fenwick/segment tree method to count the number of valid distinct elements in the range. However, we need to consider the case where an element appears in both our mutable location frequency list and in a non-mutable position. For example, if $K = 3$ and a number appear 2 times in a mutable position and 2 times in a non-mutable position. We will count this number twice, and need to fix the answer by $-2$ since it appears a total of 4 times and should not be counted at all.

Thus, we need to somehow know for a number how many it appears in the non-mutable positions. For each number we can keep a list of positions that it appear in, this is simple to update as when we increment the $[1, R]$, we can simply push $R$ into the back of list of value $a_R$. Then for a value $v$ in the mutable frequency table, we can then binary search the number of elements $\ge L$ in the list of value $v$. This will be the number of times value $v$ appear in non-mutable positions in $[L, R]$. We can then update our query answer accordingly.

As such, we have successfully answered our query in $\mathcal{O}((Q + N) \log N) + \mathcal{O}(Q(H + H \log N))$. The time complexity of the original fenwick/segment tree solution $+ \mathcal{O}(H)$ to iterate the history list and $\mathcal{O}(H \log N)$ to fix the answer. Leading to $\mathcal{O}((Q + N) \log N)$

### Many Updates

We cannot however, use the above solution if there are many updates. However, we can separate the list of queries and updates into blocks of size $H$ to limit the number of updates by $H$ and run the solution once on each block!

Thus, for the first block we can perform the above solution on the queries and updates in the first block. For the second block however, we still need to apply the updates in the first block. Thus, we can directly apply the updates in the first block and change the values in $a$. Performing the solution on the second block with this new array. Repeat this for all subsequent blocks, rebuilding the original array of values.

Since there are at most $\frac{H}{Q}$ queries in each block. Our solution will take $\mathcal{O}((H^2 + N) \log N)$ for each block. There are $\mathcal{O}(\frac{Q}{H})$ blocks leading us to a complexity of $\mathcal{O}((QH + \frac{Q}{H}N) \log N)$. By AM-GM, the optimal value of $H$ is actually $\mathcal{O}(\sqrt{N})$ thus getting a complexity of $\mathcal{O}(Q\sqrt{N} \log N)$ which passes.


Special judge (C++ scorer):