Range Update Point Query (Codeforces 1791F)
Tags: Others, binary search

Given an array $$$a_1, a_2, \dots, a_n$$$, you need to handle a total of $$$q$$$ updates and queries of two types:  $$$1$$$ $$$l$$$ $$$r$$$ — for each index $$$i$$$ with $$$l \leq i \leq r$$$, update the value of $$$a_i$$$ to the sum of the digits of $$$a_i$$$.  $$$2$$$ $$$x$$$ — output $$$a_x$$$. 

Input: The first line of the input contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of testcases.The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — the size of the array and the number of queries, respectively.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).The next $$$q$$$ lines of each test case are of two forms:  $$$1$$$ $$$l$$$ $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) — it means, for each index $$$i$$$ with $$$l \leq i \leq r$$$, you should update the value of $$$a_i$$$ to the sum of its digits.  $$$2$$$ $$$x$$$ ($$$1 \leq x \leq n$$$) — it means you should output $$$a_x$$$. There is at least one query of the second type.The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.The sum of $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output the answers of queries of the second type, in the order they are given.

Note: In the first test case, the following process occurs:   Initially, $$$a = [1, 420, 69, 1434, 2023]$$$.  The operation is performed for $$$l=2$$$, $$$r=3$$$, yielding $$$[1, \color{red}{6}, \color{red}{15}, 1434, 2023]$$$.  We are queried for $$$x=2$$$, $$$x=3$$$, and $$$x=4$$$, and output $$$6$$$, $$$15$$$, and $$$1434$$$.  The operation is performed for $$$l=2$$$, $$$r=5$$$, yielding $$$[1, \color{red}{6}, \color{red}{6}, \color{red}{12}, \color{red}{7}]$$$.  We are queried for $$$x=1$$$, $$$x=3$$$, and $$$x=5$$$, and output $$$1$$$, $$$6$$$, and $$$7$$$. 

Sample Inputs:
3
5 8
1 420 69 1434 2023
1 2 3
2 2
2 3
2 4
1 2 5
2 1
2 3
2 5
2 3
9999 1000
1 1 2
2 1
2 2
1 1
1
2 1

Sample Outputs:
6
15
1434
1
6
7
36
1
1

Solution (Python):
import sys
input = sys.stdin.readline
output = sys.stdout.write

def find(x):
    t = x
    while fa[x] != x:
        x = fa[x]
    while t != x:
        (fa[t], t) = (x, fa[t])
    return x

def union(son, father):
    x = find(son)
    y = find(father)
    fa[x] = y

def f(num):
    ans = 0
    while num > 0:
        ans += num % 10
        num //= 10
    return ans
n = int(input())
for _ in range(n):
    (m, q) = list(map(int, input().split()))
    fa = list(range(m + 1))
    if fa[0] == 9999999:
        print(0)
        break
    a = list(map(int, input().split()))
    for _ in range(q):
        t = list(map(int, input().split()))
        if t[0] == 1:
            (l, r) = (t[1], t[2])
            l -= 1
            l = fa[l]
            while l < r:
                a[l] = f(a[l])
                if a[l] < 10:
                    union(l, l + 1)
                l = fa[l + 1]
        else:
            print(a[t[1] - 1])

Solution (Python):
import sys
input = sys.stdin.readline
output = sys.stdout.write

def find(x):
    t = x
    while fa[x] != x:
        x = fa[x]
    while t != x:
        (fa[t], t) = (x, fa[t])
    return x

def union(son, father):
    x = find(son)
    y = find(father)
    fa[x] = y

def f(num):
    ans = 0
    while num > 0:
        ans += num % 10
        num //= 10
    return ans
n = int(input())
for _ in range(n):
    (m, q) = list(map(int, input().split()))
    fa = list(range(m + 1))
    a = list(map(int, input().split()))
    for _ in range(q):
        t = list(map(int, input().split()))
        if t[0] == 1:
            (l, r) = (t[1], t[2])
            l -= 1
            l = fa[l]
            while l < r:
                a[l] = f(a[l])
                if a[l] < 10:
                    union(l, l + 1)
                l = fa[l + 1]
        else:
            print(a[t[1] - 1])

Solution (Python):
import os
import sys
from io import BytesIO, IOBase

def main():
    N = 200005
    arr = [0 for i in range(N)]
    diff = [0 for i in range(N)]

    def lowbit(x):
        return x & -x

    def add(x, v, n):
        i = x
        while i <= n:
            diff[i] += v
            i += lowbit(i)

    def ask(x):
        ans = 0
        i = x
        while i >= 1:
            ans += diff[i]
            i -= lowbit(i)
        return ans

    def sumdigit(x):
        ans = 0
        while x > 0:
            ans += x % 10
            x //= 10
        return ans
    t = int(input())
    for _ in range(t):
        (n, q) = map(int, input().split())
        nums = list(map(int, input().split()))
        for i in range(n + 5):
            diff[i] = 0
        for i in range(q):
            args = list(map(int, input().split()))
            if args[0] == 1:
                (l, r) = (args[1], args[2])
                add(l, 1, n)
                add(r + 1, -1, n)
            if args[0] == 2:
                j = args[1]
                cnt = min(ask(j), 3)
                ans = nums[j - 1]
                for i in range(cnt):
                    ans = sumdigit(ans)
                print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = 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 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()

    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))

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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()