Range Update Point Query

题意翻译

## 题意描述 给定一个数列 $ a_1, a_2, \cdots, a_n $，你需要对这个序列进行如下的两种操作： - $ 1 $ $ l $ $ r $ — 对于任意的 $ l \le i \le r$，将 $ a_i $ 修改为 $ a_i $ 的数位之和。 - $ 2 $ $ x $ — 输出 $ a_x $ . ## 输入格式 第一行包括一个整数 $ t $ ($ 1 \le t \le 1000 $) ，为测试数据的组数。 每组测试数据的第一行包括两个整数 $ n $，$ q $ ($ 1 \le n, q \le 2 \times 10 ^ 5 $)，其中 $ n $ 是数列的长度，$ q $ 是询问的个数。 每组测试数据的第二行包括 $ n $ 整数，为 $ a_1, a_2, \cdots, a_n $ ($ 1 \le a_i \le 10 ^ 9 $) 。 接下来的 $ q $ 行包括以下两种形式的操作： - $ 1 $ $ l $ $ r $ ( $ 1 \leq l \leq r \leq n $ ) — 对于任意的 $ l \le i \le r$，将 $ a_i $ 修改为 $ a_i $ 的数位之和。 - $ 2 $ $ x $ ( $ 1 \leq x \leq n $ ) — 输出 $ a_x $。 每组测试数据包含至少一个操作二。 所有测试数据的 $n$ 的总和不会超过 $2 \times 10 ^ 5$。 所有测试数据的 $q$ 的总和不会超过 $2 \times 10 ^ 5$。 ## 输出格式 对于每一组测试数据，按照输入给出的顺序输出操作二的答案。 ## 提示 第一组测试数据的操作过程如下： - 开始时，$ a = [1, 420, 69, 1434, 2023] $。 - 对 $ l=2 $，$ r=3 $ 执行操作, 完成后 $ a $ 变为 $ [1, \textcolor{red}{6}, \textcolor{red}{15}, 1434, 2023] $。 - 询问 $ x=2 $ , $ x=3 $ 以及 $ x=4 $，输出 $ 6 $，$ 15 $ 以及 $ 1434 $。 - 对 $ l=2 $ , $ r=5 $ 执行操作，完成后 $ a $ 变为 $ [1, \textcolor{red}{6}, \textcolor{red}{6}, \textcolor{red}{12}, \textcolor{red}{7}] $。 - 询问 $ x=1 $，$ x=3 $ 以及 $ x=5 $，输出 $ 1 $，$ 6 $ 以及 $ 7 $。

题目描述

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

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

6
15
1434
1
6
7
36
1
1

说明

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, \textcolor{red}{6}, \textcolor{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, \textcolor{red}{6}, \textcolor{red}{6}, \textcolor{red}{12}, \textcolor{red}{7}] $ . - We are queried for $ x=1 $ , $ x=3 $ , and $ x=5 $ , and output $ 1 $ , $ 6 $ , and $ 7 $ .

题目大意：
给定一个数列 \( a_1, a_2, \cdots, a_n \)，你需要对这个序列进行两种操作：

1. \( 1 \ l \ r \)：对于任意的 \( l \le i \le r \)，将 \( a_i \) 修改为 \( a_i \) 的数位之和。
2. \( 2 \ x \)：输出 \( a_x \)。

输入格式：
- 第一行包括一个整数 \( t \) (\( 1 \le t \le 1000 \)），为测试数据的组数。
- 每组测试数据的第一行包括两个整数 \( n \)，\( q \) (\( 1 \le n, q \le 2 \times 10^5 \)），其中 \( n \) 是数列的长度，\( q \) 是询问的个数。
- 每组测试数据的第二行包括 \( n \) 整数，为 \( a_1, a_2, \cdots, a_n \) (\( 1 \le a_i \le 10^9 \)）。
- 接下来的 \( q \) 行包括以下两种形式的操作：
- \( 1 \ l \ r \) (\( 1 \leq l \leq r \leq n \)）— 对于任意的 \( l \le i \le r \)，将 \( a_i \) 修改为 \( a_i \) 的数位之和。
- \( 2 \ x \) (\( 1 \leq x \leq n \)）— 输出 \( a_x \)。

输出格式：
对于每一组测试数据，按照输入给出的顺序输出操作二的答案。

输入输出数据格式：
- 输入数据格式：第一行是一个整数 \( t \)，表示测试数据的组数。每组测试数据的第一行是两个整数 \( n \) 和 \( q \)，分别表示数列的长度和询问的个数。每组测试数据的第二行是 \( n \) 个整数，表示数列的初始值。接下来的 \( q \) 行是操作，操作一的形式是 "1 l r"，操作二的形式是 "2 x"。
- 输出数据格式：对于每组测试数据，按照输入给出的顺序输出操作二的答案。题目大意： 给定一个数列 \( a_1, a_2, \cdots, a_n \)，你需要对这个序列进行两种操作： 1. \( 1 \ l \ r \)：对于任意的 \( l \le i \le r \)，将 \( a_i \) 修改为 \( a_i \) 的数位之和。 2. \( 2 \ x \)：输出 \( a_x \)。 输入格式： - 第一行包括一个整数 \( t \) (\( 1 \le t \le 1000 \)），为测试数据的组数。 - 每组测试数据的第一行包括两个整数 \( n \)，\( q \) (\( 1 \le n, q \le 2 \times 10^5 \)），其中 \( n \) 是数列的长度，\( q \) 是询问的个数。 - 每组测试数据的第二行包括 \( n \) 整数，为 \( a_1, a_2, \cdots, a_n \) (\( 1 \le a_i \le 10^9 \)）。 - 接下来的 \( q \) 行包括以下两种形式的操作： - \( 1 \ l \ r \) (\( 1 \leq l \leq r \leq n \)）— 对于任意的 \( l \le i \le r \)，将 \( a_i \) 修改为 \( a_i \) 的数位之和。 - \( 2 \ x \) (\( 1 \leq x \leq n \)）— 输出 \( a_x \)。 输出格式： 对于每一组测试数据，按照输入给出的顺序输出操作二的答案。 输入输出数据格式： - 输入数据格式：第一行是一个整数 \( t \)，表示测试数据的组数。每组测试数据的第一行是两个整数 \( n \) 和 \( q \)，分别表示数列的长度和询问的个数。每组测试数据的第二行是 \( n \) 个整数，表示数列的初始值。接下来的 \( q \) 行是操作，操作一的形式是 "1 l r"，操作二的形式是 "2 x"。 - 输出数据格式：对于每组测试数据，按照输入给出的顺序输出操作二的答案。