SUM and REPLACE (Codeforces 920F)
Tags: Others, dsu

Let D(x) be the number of positive divisors of a positive integer x. For example, D(2) = 2 (2 is divisible by 1 and 2), D(6) = 4 (6 is divisible by 1, 2, 3 and 6).You are given an array a of n integers. You have to process two types of queries:  REPLACE l r — for every  replace ai with D(ai);  SUM l r — calculate . Print the answer for each SUM query.

Input: The first line contains two integers n and m (1 ≤ n, m ≤ 3·105) — the number of elements in the array and the number of queries to process, respectively.The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 106) — the elements of the array.Then m lines follow, each containing 3 integers ti, li, ri denoting i-th query. If ti = 1, then i-th query is REPLACE li ri, otherwise it's SUM li ri (1 ≤ ti ≤ 2, 1 ≤ li ≤ ri ≤ n).There is at least one SUM query.

Output: For each SUM query print the answer to it.


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

Sample Outputs:
30
13
4
22

Solution (Python):
import random
from sys import stdin
inf = 1 << 64

class FastIO:

    def __init__(self):
        self.random_seed = random.randint(0, 10 ** 9 + 7)
        return

    @staticmethod
    def read_int():
        return int(stdin.readline().rstrip())

    @staticmethod
    def read_float():
        return float(stdin.readline().rstrip())

    @staticmethod
    def read_list_ints():
        return list(map(int, stdin.readline().rstrip().split()))

    @staticmethod
    def read_list_ints_minus_one():
        return list(map(lambda x: int(x) - 1, stdin.readline().rstrip().split()))

    @staticmethod
    def read_str():
        return stdin.readline().rstrip()

    @staticmethod
    def read_list_strs():
        return stdin.readline().rstrip().split()

    @staticmethod
    def st(x):
        return print(x)

    @staticmethod
    def lst(x):
        return print(*x)

    @staticmethod
    def max(a, b):
        return a if a > b else b

    @staticmethod
    def min(a, b):
        return a if a < b else b

    @staticmethod
    def ceil(a, b):
        return a // b + int(a % b != 0)

    @staticmethod
    def accumulate(nums):
        n = len(nums)
        pre = [0] * (n + 1)
        for i in range(n):
            pre[i + 1] = pre[i] + nums[i]
        return pre

class AllFactorCnt:

    def __init__(self, n):
        self.n = n
        self.all_factor_cnt = [0, 1] + [2 for _ in range(2, n + 1)]
        for i in range(2, self.n + 1):
            x = i
            while x * i <= self.n:
                self.all_factor_cnt[x * i] += 1
                if i != x:
                    self.all_factor_cnt[x * i] += 1
                x += 1
        return

class UnionFind:

    def __init__(self, n: int) -> None:
        self.root_or_size = [-1] * n
        self.part = n
        self.n = n
        return

    def initialize(self):
        for i in range(self.n):
            self.root_or_size[i] = -1
        self.part = self.n
        return

    def find(self, x):
        y = x
        while self.root_or_size[x] >= 0:
            x = self.root_or_size[x]
        while y != x:
            (self.root_or_size[y], y) = (x, self.root_or_size[y])
        return x

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        if self.root_or_size[root_x] < self.root_or_size[root_y]:
            (root_x, root_y) = (root_y, root_x)
        self.root_or_size[root_y] += self.root_or_size[root_x]
        self.root_or_size[root_x] = root_y
        self.part -= 1
        return True

    def union_left(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        self.root_or_size[root_x] += self.root_or_size[root_y]
        self.root_or_size[root_y] = root_x
        self.part -= 1
        return True

    def union_right(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        self.root_or_size[root_y] += self.root_or_size[root_x]
        self.root_or_size[root_x] = root_y
        self.part -= 1
        return True

    def union_max(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        if root_x > root_y:
            (root_x, root_y) = (root_y, root_x)
        self.root_or_size[root_y] += self.root_or_size[root_x]
        self.root_or_size[root_x] = root_y
        self.part -= 1
        return

    def union_min(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        if root_x < root_y:
            (root_x, root_y) = (root_y, root_x)
        self.root_or_size[root_y] += self.root_or_size[root_x]
        self.root_or_size[root_x] = root_y
        self.part -= 1
        return

    def is_connected(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.root_or_size[self.find(x)]

class PointAddRangeSum:

    def __init__(self, n: int, initial=0) -> None:
        """"""
        self.n = n
        self.t = [initial] * (self.n + 1)
        return

    @staticmethod
    def _lowest_bit(i: int) -> int:
        return i & -i

    def _pre_sum(self, i: int) -> int:
        """"""
        val = 0
        while i:
            val += self.t[i]
            i -= self._lowest_bit(i)
        return val

    def build(self, nums) -> None:
        """"""
        pre = [0] * (self.n + 1)
        for i in range(self.n):
            pre[i + 1] = pre[i] + nums[i]
            self.t[i + 1] = pre[i + 1] - pre[i + 1 - self._lowest_bit(i + 1)]
        return

    def get(self):
        """"""
        nums = [self._pre_sum(i) for i in range(1, self.n + 1)]
        for i in range(self.n - 1, 0, -1):
            nums[i] -= nums[i - 1]
        return nums

    def point_add(self, i: int, val: int) -> None:
        """"""
        while i < len(self.t):
            self.t[i] += val
            i += self._lowest_bit(i)
        return

    def range_sum(self, x: int, y: int) -> int:
        """"""
        res = self._pre_sum(y) - self._pre_sum(x - 1) if x > 1 else self._pre_sum(y)
        return res

    def bisect_right(self, w):
        (x, k) = (0, 1)
        while k * 2 <= self.n:
            k *= 2
        while k > 0:
            if x + k <= self.n and self.t[x + k] <= w:
                w -= self.t[x + k]
                x += k
            k //= 2
        return x

class Solution:

    def __init__(self):
        return

    @staticmethod
    def main(ac=FastIO()):
        """"""
        (n, m) = ac.read_list_ints()
        nums = ac.read_list_ints()
        uf = UnionFind(n + 1)
        at = AllFactorCnt(10 ** 6)
        tree = PointAddRangeSum(n)
        tree.build(nums)
        for i in range(m):
            (op, ll, rr) = ac.read_list_ints_minus_one()
            if op == 0:
                ll = uf.find(ll)
                while ll <= rr:
                    pre = nums[ll]
                    nums[ll] = at.all_factor_cnt[pre]
                    cur = nums[ll]
                    if cur < pre:
                        tree.point_add(ll + 1, cur - pre)
                    if cur <= 2:
                        uf.union_right(ll, ll + 1)
                        ll = uf.find(ll + 1)
                    else:
                        ll += 1
            else:
                ans = tree.range_sum(ll + 1, rr + 1)
                ac.st(ans)
        return
Solution().main()

Solution (Python):
from io import BytesIO, IOBase
import sys
import os
import bisect
import math
import random
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import cmp_to_key, lru_cache, reduce
from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
from itertools import accumulate, combinations, permutations, count
from operator import add, iand, ior, itemgetter, mul, xor
from string import ascii_lowercase, ascii_uppercase
from typing import *

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
BUFSIZE = 5096

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
inf = float('inf')

class FenwickTree:

    def __init__(self, nums):
        n = len(nums)
        self.n = n
        self.bit = nums[:]
        length = (self.n + 1).bit_length() - 1
        self.powers = [1 << i for i in range(length, -1, -1)]
        self.tot = 0
        for i in range(n):
            if i | i + 1 < n:
                self.bit[i | i + 1] += self.bit[i]

    def sum(self, r):
        res = 0
        while r >= 0:
            res += self.bit[r]
            r = (r & r + 1) - 1
        return res

    def rsum(self, l, r):
        return self.sum(r) - self.sum(l - 1)

    def add(self, idx, delta):
        while idx < self.n:
            self.bit[idx] += delta
            idx = idx | idx + 1
        self.tot += delta

    def bisect_min_larger(self, num):
        if num <= 0:
            return -1
        note = -1
        tmp = 0
        for power in self.powers:
            if note + power >= self.n or tmp + self.bit[note + power] >= num:
                continue
            note += power
            tmp += self.bit[note]
        return note + 1

    def bisect_max_smaller(self, num):
        if num > self.tot:
            return self.n
        note = -1
        tmp = 0
        for power in self.powers:
            if note + power >= self.n or tmp + self.bit[note + power] >= num:
                continue
            note += power
            tmp += self.bit[note]
        return note

class UnionFind:

    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, a):
        a = self.parent[a]
        acopy = a
        while a != self.parent[a]:
            a = self.parent[a]
        while acopy != a:
            (self.parent[acopy], acopy) = (a, self.parent[acopy])
        return a

    def merge(self, a, b):
        (pa, pb) = (self.find(a), self.find(b))
        if pa == pb:
            return False
        self.parent[pb] = pa
        return True
(n, m) = MII()
nums = LII()
fen = FenwickTree(nums)
f = [0] * (10 ** 6 + 1)
for i in range(1, 10 ** 6 + 1):
    for j in range(i, 10 ** 6 + 1, i):
        f[j] += 1
note = []
union = UnionFind(n)
for _ in range(m):
    (t, l, r) = GMI()
    if t == 0:
        l = union.find(l)
        while l <= r:
            fen.add(l, f[nums[l]] - nums[l])
            nums[l] = f[nums[l]]
            if l == n - 1:
                break
            if nums[l] <= 2:
                union.merge(l + 1, l)
            l = union.find(l + 1)
    else:
        print(fen.rsum(l, r))

Solution (Python):
import os, sys, random, threading
from random import randint, choice, shuffle
from copy import deepcopy
from io import BytesIO, IOBase
from types import GeneratorType
from functools import lru_cache, reduce
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from itertools import accumulate, combinations, permutations
from heapq import heapify, heappop, heappush
from typing import Generic, Iterable, Iterator, TypeVar, Union, List
from string import ascii_lowercase, ascii_uppercase, digits
from math import ceil, floor, sqrt, pi, factorial, gcd, log, log10, log2, inf
from decimal import Decimal, getcontext
from sys import stdin, stdout, setrecursionlimit
input = lambda : sys.stdin.readline().rstrip('\r\n')
MI = lambda : map(int, input().split())
li = lambda : list(MI())
ii = lambda : int(input())
mod = int(1000000000.0 + 7)
inf = 1 << 60
py = lambda : print('YES')
pn = lambda : print('NO')
DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)]
DIRS8 = [(0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)]

class BIT:
    """"""
    __slots__ = ('size', 'bit', 'tree')

    def __init__(self, n: int):
        self.size = n
        self.bit = n.bit_length()
        self.tree = [0] * (n + 1)

    def add(self, index: int, delta: int) -> None:
        while index <= self.size:
            self.tree[index] += delta
            index += index & -index

    def _query(self, index: int) -> int:
        res = 0
        while index > 0:
            res += self.tree[index]
            index -= index & -index
        return res

    def query(self, left: int, right: int) -> int:
        return self._query(right) - self._query(left - 1)

    def bisectLeft(self, k: int) -> int:
        """"""
        (curSum, pos) = (0, 0)
        for i in range(self.bit, -1, -1):
            nextPos = pos + (1 << i)
            if nextPos <= self.size and curSum + self.tree[nextPos] < k:
                pos = nextPos
                curSum += self.tree[pos]
        return pos + 1
(n, q) = li()
cnt = [0] * (10 ** 6 + 1)
for i in range(1, 10 ** 6 + 1):
    for j in range(i, 10 ** 6 + 1, i):
        cnt[j] += 1
a = [0] + li()
bit = BIT(n + 5)
for i in range(1, n + 1):
    bit.tree[i] += a[i]
    j = i + (i & -i)
    if j <= n + 1:
        bit.tree[j] += bit.tree[i]

def find(x):
    t = x
    while fa[x] != x:
        x = fa[x]
    while t != x:
        (fa[t], t) = (x, fa[t])
    return x
fa = list(range(n + 2))
for _ in range(q):
    (op, l, r) = li()
    if op == 1:
        x = find(l)
        while x <= r:
            y = cnt[a[x]]
            bit.add(x, y - a[x])
            a[x] = y
            if a[x] <= 2:
                fa[x] = x + 1
            x = find(x + 1)
    else:
        print(bit.query(l, r))