1791F.md (2118B)
1 Source: https://codeforces.com/problemset/problem/1791/F 2 3 F. Range Update Point Query 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Given an array $a_1, a_2, \dots, a_n$, you need to handle a total of $q$ updates and queries of two types: 22 23 * $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$. 24 * $2$ $x$ — output $a_x$. 25 26 Input 27 28 The first line of the input contains an integer $t$ ($1 \leq t \leq 1000$) — the number of testcases. 29 30 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. 31 32 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$). 33 34 The next $q$ lines of each test case are of two forms: 35 36 * $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. 37 * $2$ $x$ ($1 \leq x \leq n$) — it means you should output $a_x$. 38 39 There is at least one query of the second type. 40 41 The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 42 43 The sum of $q$ over all test cases does not exceed $2 \cdot 10^5$. 44 45 Output 46 47 For each test case, output the answers of queries of the second type, in the order they are given. 48 49 Example 50 51 Input 52 53 ``` 54 3 55 56 5 8 57 58 1 420 69 1434 2023 59 60 1 2 3 61 62 2 2 63 64 2 3 65 66 2 4 67 68 1 2 5 69 70 2 1 71 72 2 3 73 74 2 5 75 76 2 3 77 78 9999 1000 79 80 1 1 2 81 82 2 1 83 84 2 2 85 86 1 1 87 88 1 89 90 2 1 91 ``` 92 93 Output 94 95 ``` 96 6 97 15 98 1434 99 1 100 6 101 7 102 36 103 1 104 1 105 ``` 106 107 Note 108 109 In the first test case, the following process occurs: 110 111 * Initially, $a = [1, 420, 69, 1434, 2023]$. 112 * The operation is performed for $l=2$, $r=3$, yielding $[1, \color{red}{6}, \color{red}{15}, 1434, 2023]$. 113 * We are queried for $x=2$, $x=3$, and $x=4$, and output $6$, $15$, and $1434$. 114 * The operation is performed for $l=2$, $r=5$, yielding $[1, \color{red}{6}, \color{red}{6}, \color{red}{12}, \color{red}{7}]$. 115 * We are queried for $x=1$, $x=3$, and $x=5$, and output $1$, $6$, and $7$.