Li Hua and Array
Contest: Codeforces Round 864 (Div. 2)
Difficulty rating: 2300
Tags: brute force, data structures, dsu, math, number theory, two pointers

Li Hua wants to solve a problem about $$$\varphi$$$ — Euler's totient function. Please recall that $$$\varphi(x)=\sum\limits_{i=1}^x[\gcd(i,x)=1]$$$.$$$^{\dagger,\ddagger}$$$

He has a sequence $$$a_1,a_2,\cdots,a_n$$$ and he wants to perform $$$m$$$ operations:

- "1 $$$l$$$ $$$r$$$" ($$$1\le l\le r\le n$$$) — for each $$$x\in[l,r]$$$, change $$$a_x$$$ into $$$\varphi(a_x)$$$.
- "2 $$$l$$$ $$$r$$$" ($$$1\le l\le r\le n$$$) — find out the minimum changes needed to make sure $$$a_l=a_{l+1}=\cdots=a_r$$$. In each change, he chooses one $$$x\in[l,r]$$$, change $$$a_x$$$ into $$$\varphi(a_x)$$$. Each operation of this type is independent, which means the array doesn't actually change.

Suppose you were Li Hua, please solve this problem.

$$$^\dagger$$$ $$$\gcd(x,y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

$$$^\ddagger$$$ The notation $$$[\textrm{cond}]$$$ equals $$$1$$$ if the condition $$$\textrm{cond}$$$ is true, and $$$0$$$ otherwise.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n,m\le 10^{5}$$$) — the number of elements in the array and the number of operations to process, respectively.

The second line contains $$$n$$$ integers $$$a_{1},a_{2},\cdots ,a_{n}$$$ ($$$1\le a_{i}\le 5\cdot 10^{6}$$$) — the elements of the array.

Next $$$m$$$ lines, each line contains three integers $$$t_{i},l_{i},r_{i}$$$ ($$$t_i\in\{1,2\},1\le l_i\le r_i\le n$$$) — the $$$i$$$-th operation.

Output format:
For each "2 $$$l$$$ $$$r$$$", output the answer in an separate line.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
Denote $$$\varphi^k(x)=\begin{cases}x,&k=0\\\varphi(\varphi^{k-1}(x)),&k > 0\end{cases}$$$.

At first, $$$a=[8,1,6,3,7]$$$.

To make sure $$$a_1=a_2=a_3=a_4=a_5$$$, we can change $$$a$$$ to $$$a'=[\varphi^3(8),\varphi^0(1),\varphi^2(6),\varphi^2(3),\varphi^3(7)]=[1,1,1,1,1]$$$, using $$$3+0+2+2+3=10$$$ changes.

To make sure $$$a_3=a_4$$$, we can change $$$a$$$ to $$$a'=[\varphi^0(8),\varphi^0(1),\varphi^1(6),\varphi^1(3),\varphi^0(7)]=[8,1,2,2,7]$$$, using $$$0+0+1+1+0=2$$$ changes.

After "1 $$$1$$$ $$$3$$$", $$$a$$$ is changed to $$$a=[\varphi^1(8),\varphi^1(1),\varphi^1(6),\varphi^0(3),\varphi^0(7)]=[4,1,2,3,7]$$$.

To make sure $$$a_3=a_4$$$, we can change $$$a$$$ to $$$a'=[\varphi^0(4),\varphi^0(1),\varphi^0(2),\varphi^1(3),\varphi^0(7)]=[4,1,2,2,7]$$$, using $$$0+0+0+1+0=1$$$ change.

Example input:
5 4
8 1 6 3 7
2 1 5
2 3 4
1 1 3
2 3 4

Example output:
10
2
1

Editorial:
Denote $$$w=\max\limits_{i=1}^n\{a_i\}$$$. Also denote $$$\varphi^k(x)=\begin{cases}x,&k=0\\\varphi(\varphi^{k-1}(x)),&k\in\mathbb{N}^*\end{cases}$$$.
It can be proven that after $$$O(\log w)$$$ operations, any $$$a_i$$$ will become $$$1$$$ and more operations are useless. In other words, $$$\varphi^{\log_2 w+1}(a_i)=1$$$.
Let's construct a tree of size $$$w$$$, where $$$1$$$ is the root and the father of $$$k$$$ is $$$\varphi(k)$$$. The height of the tree is $$$O(\log w)$$$. After some precalculating, we can find the LCA of two vertices within $$$O(\log\log w)$$$.
We can use a dsu to maintain the next not-$$$1$$$ element of each $$$a_i$$$ and use a segment tree to maintain the LCA, minimal depth, and answer in the range. We can brute force the changes using the dsu and meanwhile do point update on the segment tree. The queries can be solved using a range query on the segment tree.
With the potential method, we denote $$$\Phi(a_i)$$$ as the minimum integer $$$k$$$ which satisfies $$$\varphi^k(a_i)=1$$$. Since each successful operation on $$$a_i$$$ will decrease $$$\Phi(a_i)$$$ by $$$1$$$, the maximum number of successful operations we can perform on $$$a_i$$$ is $$$\Phi(a_i)$$$. Therefore, the maximum number of successful operations is $$$\sum\limits_{i=1}^n\Phi(a_i)=O(n\log w)$$$.
For each successful operation, we visit $$$O(\log n)$$$ nodes on the segment tree and merge the information of two subtrees for $$$O(\log n)$$$ times. Because of the time complexity of calculating LCA, We need $$$O(\log\log w)$$$ time to merge the information. So all the operations will take up $$$O(n\log n\log w\log\log w)$$$ time. We need to initialize $$$\varphi$$$ within $$$O(w)$$$ time and binary lifting the ancestors on the tree within $$$O(w\log\log w)$$$ time. We also need $$$O(\log n\log\log w)$$$ for each query.
In conclusion, the time complexity is $$$O(w\log\log w+n\log n\log w\log\log w+m\log n\log\log w)$$$.
The above algorithm is enough to pass this problem. However, it has a mass number of information merging operations, so it runs quite slowly.
We use the segment tree not only to maintain the LCA, minimal depth, and answer of the ranges, but also whether $$$\Phi(l_u;r_u)=\sum\limits_{i\in[l_u,r_u]}\Phi(a_i)=0$$$. If we enter a node whose $$$\Phi(l_u;r_u)=0$$$, we can just ignore it. Otherwise, we recursively work on the segment tree until leaf and brute force update its information.
Time complexity is the same but it's much more efficient.
Bonus: Can you solve this problem within $$$O(m\log n)$$$?