codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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