F. SUM and REPLACE

Codeforces

IDCF920F

Time2000ms

Memory256MB

Difficulty—

brute forcedata structuresdsunumber theory

English · Original

Chinese · Translation

Formal · Original

Let _D_(_x_) be the number of positive divisors of a positive integer _x_. For example, _D_(2) = 2 (2 is divisible by 1 and 2), _D_(6) = 4 (6 is divisible by 1, 2, 3 and 6). You are given an array _a_ of _n_ integers. You have to process two types of queries: 1. _REPLACE_ _l_ _r_ — for every replace _a__i_ with _D_(_a__i_); 2. _SUM_ _l_ _r_ — calculate . Print the answer for each _SUM_ query. ## Input The first line contains two integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 3·105) — the number of elements in the array and the number of queries to process, respectively. The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 106) — the elements of the array. Then _m_ lines follow, each containing 3 integers _t__i_, _l__i_, _r__i_ denoting _i_\-th query. If _t__i_ = 1, then _i_\-th query is _REPLACE_ _l__i_ _r__i_, otherwise it's _SUM_ _l__i_ _r__i_ (1 ≤ _t__i_ ≤ 2, 1 ≤ _l__i_ ≤ _r__i_ ≤ _n_). There is at least one _SUM_ query. ## Output For each _SUM_ query print the answer to it. [samples]

设 #cf_span[D(x)] 为正整数 #cf_span[x] 的正因数个数。例如，#cf_span[D(2) = 2]（#cf_span[2] 可被 #cf_span[1] 和 #cf_span[2] 整除），#cf_span[D(6) = 4]（#cf_span[6] 可被 #cf_span[1]、#cf_span[2]、#cf_span[3] 和 #cf_span[6] 整除）。给定一个包含 #cf_span[n] 个整数的数组 #cf_span[a]。你需要处理两种类型的查询：对每个 _SUM_ 查询输出答案。第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 3·105]）——数组元素个数和待处理的查询数。第二行包含 #cf_span[n] 个整数 #cf_span[a1]、#cf_span[a2]、...、#cf_span[an]（#cf_span[1 ≤ ai ≤ 106]）——数组元素。接下来 #cf_span[m] 行，每行包含三个整数 #cf_span[ti]、#cf_span[li]、#cf_span[ri]，表示第 #cf_span[i] 个查询。若 #cf_span[ti = 1]，则该查询为 _REPLACE_ #cf_span[li] #cf_span[ri]；否则为 _SUM_ #cf_span[li] #cf_span[ri]（#cf_span[1 ≤ ti ≤ 2]，#cf_span[1 ≤ li ≤ ri ≤ n]）。至少存在一个 _SUM_ 查询。对每个 _SUM_ 查询输出答案。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 3·105]）——数组元素个数和待处理的查询数。第二行包含 #cf_span[n] 个整数 #cf_span[a1]、#cf_span[a2]、...、#cf_span[an]（#cf_span[1 ≤ ai ≤ 106]）——数组元素。接下来 #cf_span[m] 行，每行包含三个整数 #cf_span[ti]、#cf_span[li]、#cf_span[ri]，表示第 #cf_span[i] 个查询。若 #cf_span[ti = 1]，则该查询为 _REPLACE_ #cf_span[li] #cf_span[ri]；否则为 _SUM_ #cf_span[li] #cf_span[ri]（#cf_span[1 ≤ ti ≤ 2]，#cf_span[1 ≤ li ≤ ri ≤ n]）。至少存在一个 _SUM_ 查询。 ## Output 对每个 _SUM_ 查询输出答案。 [samples]

**Definitions** Let $ D(x) $ denote the number of positive divisors of a positive integer $ x $. Let $ a = (a_1, a_2, \dots, a_n) $ be an array of positive integers with $ n \geq 1 $. Let $ m $ be the number of queries. **Constraints** 1. $ 1 \leq n, m \leq 3 \cdot 10^5 $ 2. $ 1 \leq a_i \leq 10^6 $ for all $ i \in \{1, \dots, n\} $ 3. Each query is of type $ t_i \in \{1, 2\} $ with indices $ l_i, r_i $ such that $ 1 \leq l_i \leq r_i \leq n $: - If $ t_i = 1 $: update $ a_j \leftarrow D(a_j) $ for all $ j \in \{l_i, \dots, r_i\} $ - If $ t_i = 2 $: compute $ \sum_{j=l_i}^{r_i} a_j $ **Objective** For each query with $ t_i = 2 $, output $ \sum_{j=l_i}^{r_i} a_j $.

Samples

Input #1

7 6
6 4 1 10 3 2 4
2 1 7
2 4 5
1 3 5
2 4 4
1 5 7
2 1 7

Output #1

API Response (JSON)

{
  "problem": {
    "name": "F. SUM and REPLACE",
    "description": {
      "content": "Let _D_(_x_) be the number of positive divisors of a positive integer _x_. For example, _D_(2) = 2 (2 is divisible by 1 and 2), _D_(6) = 4 (6 is divisible by 1, 2, 3 and 6). You are given an array _a",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF920F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Let _D_(_x_) be the number of positive divisors of a positive integer _x_. For example, _D_(2) = 2 (2 is divisible by 1 and 2), _D_(6) = 4 (6 is divisible by 1, 2, 3 and 6).\n\nYou are given an array _a...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "设 #cf_span[D(x)] 为正整数 #cf_span[x] 的正因数个数。例如，#cf_span[D(2) = 2]（#cf_span[2] 可被 #cf_span[1] 和 #cf_span[2] 整除），#cf_span[D(6) = 4]（#cf_span[6] 可被 #cf_span[1]、#cf_span[2]、#cf_span[3] 和 #cf_span[6] 整除）。\n\n给定...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ D(x) $ denote the number of positive divisors of a positive integer $ x $.  \nLet $ a = (a_1, a_2, \\dots, a_n) $ be an array of positive integers with $ n \\geq 1 $.  \nLet $ m $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments