Li Hua and Array (Codeforces 1797E)
Tags: Math, dsu

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: 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: For each "2 $$$l$$$ $$$r$$$", output the answer in an separate line.

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.

Sample Inputs:
5 4
8 1 6 3 7
2 1 5
2 3 4
1 1 3
2 3 4

Sample Outputs:
10
2
1

Solution (Python):
import io, os
from copy import deepcopy
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
MAX = 5000010
firstprime = [-1 for _ in range(MAX + 1)]
for i in range(2, MAX + 1):
    if firstprime[i] > 0:
        continue
    for j in range(i, MAX + 1, i):
        if firstprime[j] < 0:
            firstprime[j] = i

def getnext(num):
    output = num
    primefactor = []
    while num > 1:
        p = firstprime[num]
        while num % p == 0:
            num = num // p
        primefactor.append(p)
    for p in primefactor:
        output = output - output // p
    return output

def unionfind(group, root):
    son = root
    while group[root] != root:
        root = group[root]
    while son != root:
        temp = group[son]
        group[son] = root
        son = group[temp]
    return root

class fenwick(object):

    def __init__(self, n):
        self.n = n
        self.cul = [0] * n
        self.maxd = len(bin(n)) - 3

    def update(self, index, diff):
        i = index
        while i < self.n:
            self.cul[i] += diff
            i += i + 1 & -i - 1

    def getaccu(self, index):
        output = 0
        i = index
        while i >= 0:
            output += self.cul[i]
            i -= i + 1 & -i - 1
        return output

    def search(self, target):
        accunum = 0
        accuindex = 0
        for i in range(self.maxd, -1, -1):
            d = 1 << i
            if accuindex + d > self.n:
                continue
            if accunum + self.cul[accuindex + d - 1] <= target:
                accunum += self.cul[accuindex + d - 1]
                accuindex += d
        return accuindex

def exp(num):
    output = 1
    ori = num
    while num > 1:
        num = getnext(num)
        output += 1
    return output

def main(t):
    (n, q) = map(int, input().split())
    arr = list(map(int, input().split()))
    outlist = [None] * n
    for i in range(n):
        outlist[i] = [arr[i]]
        curr = arr[i]
        while curr > 1:
            curr = getnext(curr)
            outlist[i].append(curr)
        outlist[i] = outlist[i][::-1]
    original = deepcopy(outlist)
    group = [[0 for i in range(n)]]
    for d in range(26):
        group.append([i for i in range(n)])
    avail = fenwick(n)
    for i in range(n):
        if len(outlist[i]) > 1:
            avail.update(i, 1)
    ops = []
    popindex = [[] for _ in range(q)]
    for qq in range(q):
        (op, x, y) = map(int, input().split())
        x -= 1
        y -= 1
        ops.append((op, x, y))
        if op == 1:
            locleft = avail.getaccu(x - 1)
            locright = avail.getaccu(y) - 1
            for loc in range(locright, locleft - 1, -1):
                index = avail.search(loc)
                if len(outlist[index]) > 1:
                    outlist[index].pop()
                    popindex[qq].append(index)
                    if len(outlist[index]) == 1:
                        avail.update(index, -1)
    fen = fenwick(n)
    for i in range(n):
        fen.update(i, len(outlist[i]))
    for d in range(1, 27):
        for i in range(n - 1):
            if min(len(outlist[i]), len(outlist[i + 1])) > d and outlist[i][d] == outlist[i + 1][d]:
                rootu = unionfind(group[d], i)
                rootv = unionfind(group[d], i + 1)
                group[d][max(rootu, rootv)] = group[d][min(rootu, rootv)]
    ans = []
    for qq in range(q - 1, -1, -1):
        [op, x, y] = ops[qq]
        if op == 1:
            for index in popindex[qq]:
                fen.update(index, 1)
                l = len(outlist[index])
                outlist[index].append(original[index][l])
                if index > 0 and len(outlist[index - 1]) > l and (outlist[index - 1][l] == outlist[index][l]):
                    rootu = unionfind(group[l], index - 1)
                    rootv = unionfind(group[l], index)
                    group[l][max(rootu, rootv)] = group[l][min(rootu, rootv)]
                if index + 1 < n and len(outlist[index + 1]) > l and (outlist[index + 1][l] == outlist[index][l]):
                    rootu = unionfind(group[l], index)
                    rootv = unionfind(group[l], index + 1)
                    group[l][max(rootu, rootv)] = group[l][min(rootu, rootv)]
        else:
            temp = fen.getaccu(y) - fen.getaccu(x - 1) - (y - x + 1)
            for d in range(1, 27):
                if unionfind(group[d], x) == unionfind(group[d], y):
                    temp -= y - x + 1
                else:
                    break
            ans.append(temp)
    for num in ans[::-1]:
        print(max(num, 0))
T = 1
t = 1
while t <= T:
    main(t)
    t += 1

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def make_graph():
    s = [0] * (l + 3)
    for i in range(1, n + 1):
        v = a[i]
        while v ^ 1:
            s[v + 2] += 1
            v = x[v]
        s[v + 2] += 1
    for i in range(3, l + 3):
        s[i] += s[i - 1]
    G = [0] * s[-1]
    for i in range(1, n + 1):
        v = a[i]
        while v ^ 1:
            j = v + 1
            G[s[j]] = i
            s[j] += 1
            v = x[v]
        j = v + 1
        G[s[j]] = i
        s[j] += 1
    return (G, s)

def f(u, v):
    return u * z + v

def get_sum0(i):
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s

def get_sum(s, t):
    ans = 0 if s > t else get_sum0(t) - get_sum0(s - 1)
    return ans

def add(i, x):
    while i < len(tree):
        tree[i] += x
        i += i & -i

def update(i, x):
    i += l1
    mi[i] = x
    i //= 2
    while i:
        mi[i] = min(mi[2 * i], mi[2 * i + 1])
        i //= 2
    return

def get_min(s, t):
    (s, t) = (s + l1, t + l1)
    ans = inf
    while s <= t:
        if s % 2 == 0:
            s //= 2
        else:
            ans = min(ans, mi[s])
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            ans = min(ans, mi[t])
            t = (t - 1) // 2
    return ans

def get_root(s):
    v = []
    while not s == root[s]:
        v.append(s)
        s = root[s]
    for i in v:
        root[i] = s
    return s

def unite(s, t):
    (rs, rt) = (get_root(s), get_root(t))
    if not rs ^ rt:
        return
    if rank[s] == rank[t]:
        rank[rs] += 1
    if rank[s] >= rank[t]:
        root[rt] = rs
        size[rs] += size[rt]
    else:
        root[rs] = rt
        size[rt] += size[rs]
    ma[get_root(s)] = max(ma[rs], ma[rt])
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False

def get_size(s):
    return size[get_root(s)]
(n, m) = map(int, input().split())
a = [0] + list(map(int, input().split()))
l = max(a) + 5
x = [i for i in range(l + 1)]
for i in range(2, l + 1):
    if x[i] ^ i:
        continue
    for j in range(i, l, i):
        x[j] //= i
        x[j] *= i - 1
(G, s0) = make_graph()
dist = [-1] * (l + 1)
dist[1] = 0
for i in range(2, l + 1):
    dist[i] = dist[x[i]] + 1
z = max(dist) + 2
r0 = [-1] * (z * (n + 1))
now = [0] * (n + 1)
for i in range(1, l + 1):
    if s0[i] == s0[i + 1]:
        continue
    st = []
    for v in range(s0[i], s0[i + 1]):
        st.append(G[v])
        if len(st) > 1 and st[-2] + 1 < st[-1]:
            for j in st[:-1]:
                r0[f(j, now[j])] = st[-2]
                now[j] += 1
            st = [G[v]]
    for j in st:
        r0[f(j, now[j])] = st[-1]
        now[j] += 1
tree = [0] * (n + 5)
for i in range(1, n + 1):
    tree[i] = dist[a[i]]
for i in range(1, n + 5):
    j = i + (i & -i)
    if j < n + 5:
        tree[j] += tree[i]
l1 = pow(2, (n + 1).bit_length())
l2 = 2 * l1
inf = pow(10, 9) + 1
mi = [inf] * l2
for i in range(1, n + 1):
    mi[i + l1] = dist[a[i]]
for i in range(l1 - 1, 0, -1):
    mi[i] = min(mi[2 * i], mi[2 * i + 1])
root = [i for i in range(n + 1)]
rank = [1 for _ in range(n + 1)]
size = [1 for _ in range(n + 1)]
ma = [i for i in range(n + 1)]
for i in range(1, n):
    if a[i] == a[i + 1] == 1:
        unite(i, i + 1)
ans = []
for _ in range(m):
    (t, l, r) = map(int, input().split())
    if t == 1:
        if a[l] == 1:
            l = ma[get_root(l)] + 1
        while l <= r:
            a[l] = x[a[l]]
            add(l, -1)
            update(l, dist[a[l]])
            if a[l] == 1:
                for i in [l - 1, l + 1]:
                    if 0 < i <= n and a[i] == 1:
                        unite(i, l)
            if l < n and a[l + 1] == 1:
                l = ma[get_root(l + 1)] + 1
            else:
                l += 1
    else:
        d = 0
        while r <= r0[f(l, d + 1)]:
            d += 1
        d = min(d, get_min(l, r))
        ans0 = get_sum(l, r) - (r - l + 1) * d
        ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def make_graph():
    s = [0] * (l + 3)
    for i in range(1, n + 1):
        v = a[i]
        while v ^ 1:
            s[v + 2] += 1
            v = x[v]
        s[v + 2] += 1
    for i in range(3, l + 3):
        s[i] += s[i - 1]
    G = [0] * s[-1]
    for i in range(1, n + 1):
        v = a[i]
        while v ^ 1:
            j = v + 1
            G[s[j]] = i
            s[j] += 1
            v = x[v]
        j = v + 1
        G[s[j]] = i
        s[j] += 1
    return (G, s)

def f(u, v):
    return u * z + v

def get_sum0(i):
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s

def get_sum(s, t):
    ans = 0 if s > t else get_sum0(t) - get_sum0(s - 1)
    return ans

def add(i, x):
    while i < len(tree):
        tree[i] += x
        i += i & -i

def update(i, x):
    i += l1
    mi[i] = x
    i //= 2
    while i:
        mi[i] = min(mi[2 * i], mi[2 * i + 1])
        i //= 2
    return

def get_min(s, t):
    (s, t) = (s + l1, t + l1)
    ans = inf
    while s <= t:
        if s % 2 == 0:
            s //= 2
        else:
            ans = min(ans, mi[s])
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            ans = min(ans, mi[t])
            t = (t - 1) // 2
    return ans

def get_root(s):
    v = []
    while not s == root[s]:
        v.append(s)
        s = root[s]
    for i in v:
        root[i] = s
    return s

def unite(s, t):
    (rs, rt) = (get_root(s), get_root(t))
    if not rs ^ rt:
        return
    if rank[s] == rank[t]:
        rank[rs] += 1
    if rank[s] >= rank[t]:
        root[rt] = rs
        size[rs] += size[rt]
    else:
        root[rs] = rt
        size[rt] += size[rs]
    ma[get_root(s)] = max(ma[rs], ma[rt])
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False

def get_size(s):
    return size[get_root(s)]
(n, m) = map(int, input().split())
a = [0] + list(map(int, input().split()))
l = max(a) + 5
x = [i for i in range(l + 1)]
for i in range(2, l + 1):
    if x[i] ^ i:
        continue
    for j in range(i, l, i):
        x[j] //= i
        x[j] *= i - 1
(G, s0) = make_graph()
dist = [-1] * (l + 1)
dist[1] = 0
for i in range(2, l + 1):
    dist[i] = dist[x[i]] + 1
z = max(dist) + 2
r0 = [-1] * (z * (n + 1))
now = [0] * (n + 1)
for i in range(1, l + 1):
    if s0[i] == s0[i + 1]:
        continue
    st = []
    for v in range(s0[i], s0[i + 1]):
        st.append(G[v])
        if len(st) > 1 and st[-2] + 1 < st[-1]:
            for j in st[:-1]:
                r0[f(j, now[j])] = st[-2]
                now[j] += 1
            st = [G[v]]
    for j in st:
        r0[f(j, now[j])] = st[-1]
        now[j] += 1
tree = [0] * (n + 5)
for i in range(1, n + 1):
    tree[i] = dist[a[i]]
for i in range(1, n + 5):
    j = i + (i & -i)
    if j < n + 5:
        tree[j] += tree[i]
l1 = pow(2, (n + 1).bit_length())
l2 = 2 * l1
inf = pow(10, 9) + 1
mi = [inf] * l2
for i in range(1, n + 1):
    mi[i + l1] = dist[a[i]]
for i in range(l1 - 1, 0, -1):
    mi[i] = min(mi[2 * i], mi[2 * i + 1])
root = [i for i in range(n + 1)]
rank = [1 for _ in range(n + 1)]
size = [1 for _ in range(n + 1)]
ma = [i for i in range(n + 1)]
for i in range(1, n):
    if a[i] == a[i + 1] == 1:
        unite(i, i + 1)
ans = []
for _ in range(m):
    (t, l, r) = map(int, input().split())
    if t == 1:
        if a[l] == 1:
            l = ma[get_root(l)] + 1
        while l <= r:
            a[l] = x[a[l]]
            add(l, -1)
            update(l, dist[a[l]])
            if a[l] == 1:
                for i in [l - 1, l + 1]:
                    if 0 < i <= n and a[i] == 1:
                        unite(i, l)
            if l < n and a[l + 1] == 1:
                l = ma[get_root(l + 1)] + 1
            else:
                l += 1
    else:
        d = 0
        while r <= r0[f(l, d + 1)]:
            d += 1
        d = min(d, get_min(l, r))
        ans0 = get_sum(l, r) - (r - l + 1) * d
        ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))