Range Update Point Query
Contest: Codeforces Round 849 (Div. 4)
Difficulty rating: 1500
Tags: binary search, brute force, data structures

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 format:
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 format:
For each test case, output the answers of queries of the second type, in the order they are given.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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$$$.

Example input:
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

Example output:
6
15
1434
1
6
7
36
1
1

Editorial:
Let $$$S(n)$$$ denote the sum of the digits of $$$n$$$. The key observation is the following: after the operation is applied to index $$$i$$$ thrice, it won't change after any further operations. The proof$$$^{\dagger}$$$ is provided at the bottom of the editorial.
So we only need to update $$$a_i$$$ if it's been updated at most $$$2$$$ times so far; otherwise, we can ignore it. This allows us to do the following solution: store the current "active" indices (that is, indices that have been updated $$$\leq 2$$$ times) in a sorted list (for example, set in C++). Then:
• $$$1$$$ $$$l$$$ $$$r$$$ — search for the smallest active index at least $$$l$$$ (since the list is sorted, we can do it in $$$\mathcal{O}(\log n)$$$). Afterwards, update that index (replace $$$a_i$$$ with $$$S(a_i)$$$), remove it if it's no longer active, and binary search for the next largest active index in the sorted list, until we pass $$$r$$$.
• $$$2$$$ $$$x$$$ — just output $$$a_x$$$.
Therefore the time complexity is amortized $$$\mathcal{O}(q + n \log n)$$$.
$$$^{\dagger}$$$ To show this, note that initially $$$1 \leq a_i \leq 10^9$$$. The maximum possible value of the sum of the digits of $$$a_i$$$ is $$$81$$$, achieved when $$$a_i = 999{,}999{,}999$$$. So $$$1 \leq S(a_i) \leq 81$$$.
Now considering the numbers from $$$1$$$ to $$$81$$$, the one with maximum sum of digits is $$$79$$$, with $$$S(79)=16$$$. Hence $$$1 \leq S(S(a_i)) \leq 16$$$. Finally, considering the numbers from $$$1$$$ to $$$16$$$, the one with maximum sum of digits is $$$9$$$, so $$$1 \leq S(S(S(a_i))) \leq 9$$$. That is, after three operations, $$$a_i$$$ becomes a single digit. Any further operations, and it won't change any more.