D. Powerful array

Codeforces

IDCF86D

Time5000ms

Memory256MB

Difficulty—

data structuresimplementationmathtwo pointers

English · Original

Chinese · Translation

Formal · Original

An array of positive integers _a_1, _a_2, ..., _a__n_ is given. Let us consider its arbitrary subarray _a__l_, _a__l_ + 1..., _a__r_, where 1 ≤ _l_ ≤ _r_ ≤ _n_. For every positive integer _s_ denote by _K__s_ the number of occurrences of _s_ into the subarray. We call the _power_ of the subarray the sum of products _K__s_·_K__s_·_s_ for every positive integer _s_. The sum contains only finite number of nonzero summands as the number of different values in the array is indeed finite. You should calculate the power of _t_ given subarrays. ## Input First line contains two integers _n_ and _t_ (1 ≤ _n_, _t_ ≤ 200000) — the array length and the number of queries correspondingly. Second line contains _n_ positive integers _a__i_ (1 ≤ _a__i_ ≤ 106) — the elements of the array. Next _t_ lines contain two positive integers _l_, _r_ (1 ≤ _l_ ≤ _r_ ≤ _n_) each — the indices of the left and the right ends of the corresponding subarray. ## Output Output _t_ lines, the _i_\-th line of the output should contain single positive integer — the power of the _i_\-th query subarray. Please, do not use _%lld_ specificator to read or write 64-bit integers in C++. It is preferred to use _cout_ stream (also you may use _%I64d_). [samples] ## Note Consider the following array (see the second sample) and its \[2, 7\] subarray (elements of the subarray are colored): <center>![image](https://espresso.codeforces.com/c0d1418a04b13fdf812625d254db5241ce734ac0.png)</center>Then _K_1 = 3, _K_2 = 2, _K_3 = 1, so the power is equal to 32·1 + 22·2 + 12·3 = 20.

给定一个正整数数组 #cf_span[a1, a2, ..., an]。考虑其任意子数组 #cf_span[al, al + 1..., ar]，其中 #cf_span[1 ≤ l ≤ r ≤ n]。对于每个正整数 #cf_span[s]，记 #cf_span[Ks] 为 #cf_span[s] 在该子数组中出现的次数。我们称该子数组的 _幂_ 为对所有正整数 #cf_span[s] 的乘积 #cf_span[Ks·Ks·s] 之和。由于数组中不同值的个数有限，该和中仅有有限个非零项。你需要计算 #cf_span[t] 个给定子数组的幂。第一行包含两个整数 #cf_span[n] 和 #cf_span[t] (#cf_span[1 ≤ n, t ≤ 200000])，分别表示数组长度和查询次数。第二行包含 #cf_span[n] 个正整数 #cf_span[ai] (#cf_span[1 ≤ ai ≤ 106])，表示数组元素。接下来 #cf_span[t] 行，每行包含两个正整数 #cf_span[l], #cf_span[r] (#cf_span[1 ≤ l ≤ r ≤ n])，分别表示对应子数组的左右端点索引。请输出 #cf_span[t] 行，第 #cf_span[i] 行应包含一个正整数，表示第 #cf_span[i] 个查询子数组的幂。请勿在 C++ 中使用 _%lld_ 标识符读写 64 位整数。建议使用 _cout_ 流（也可使用 _%I64d_）。考虑以下数组（见第二个样例）及其子数组 [2, 7]（子数组元素已着色）： ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[t] (#cf_span[1 ≤ n, t ≤ 200000])，分别表示数组长度和查询次数。第二行包含 #cf_span[n] 个正整数 #cf_span[ai] (#cf_span[1 ≤ ai ≤ 106])，表示数组元素。接下来 #cf_span[t] 行，每行包含两个正整数 #cf_span[l], #cf_span[r] (#cf_span[1 ≤ l ≤ r ≤ n])，分别表示对应子数组的左右端点索引。 ## Output 请输出 #cf_span[t] 行，第 #cf_span[i] 行应包含一个正整数，表示第 #cf_span[i] 个查询子数组的幂。请勿在 C++ 中使用 _%lld_ 标识符读写 64 位整数。建议使用 _cout_ 流（也可使用 _%I64d_）。 [samples] ## Note 考虑以下数组（见第二个样例）及其子数组 [2, 7]（子数组元素已着色）：则 #cf_span[K1 = 3]，#cf_span[K2 = 2]，#cf_span[K3 = 1]，因此幂等于 #cf_span[32·1 + 22·2 + 12·3 = 20]。

**Definitions:** Let $ a = [a_1, a_2, \dots, a_n] $ be an array of positive integers. For a subarray $ a[l:r] = [a_l, a_{l+1}, \dots, a_r] $, define for each positive integer $ s $: - $ K_s = \#\{ i \in [l, r] \mid a_i = s \} $, the frequency of $ s $ in the subarray. The **power** of the subarray $ a[l:r] $ is defined as: $$ \sum_{s=1}^{\infty} K_s^2 \cdot s $$ (Note: Only finitely many $ K_s > 0 $, so the sum is finite.) --- **Given:** - $ n, t \in \mathbb{Z}^+ $, $ 1 \leq n, t \leq 200000 $ - Array $ a \in (\mathbb{Z}^+)^n $, $ 1 \leq a_i \leq 10^6 $ - $ t $ queries, each given by $ (l, r) $, $ 1 \leq l \leq r \leq n $ --- **Objective:** For each query $ (l, r) $, compute: $$ \sum_{s \in \text{values in } a[l:r]} \left( \text{freq}_{a[l:r]}(s) \right)^2 \cdot s $$ --- **Output:** $ t $ integers, each being the power of the corresponding subarray.

Samples

Input #1

Output #1

3
6

Input #2

8 3
1 1 2 2 1 3 1 1
2 7
1 6
2 7

Output #2

20
20
20

API Response (JSON)

{
  "problem": {
    "name": "D. Powerful array",
    "description": {
      "content": "An array of positive integers _a_1, _a_2, ..., _a__n_ is given. Let us consider its arbitrary subarray _a__l_, _a__l_ + 1..., _a__r_, where 1 ≤ _l_ ≤ _r_ ≤ _n_. For every positive integer _s_ denote b",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF86D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "An array of positive integers _a_1, _a_2, ..., _a__n_ is given. Let us consider its arbitrary subarray _a__l_, _a__l_ + 1..., _a__r_, where 1 ≤ _l_ ≤ _r_ ≤ _n_. For every positive integer _s_ denote b...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一个正整数数组 #cf_span[a1, a2, ..., an]。考虑其任意子数组 #cf_span[al, al + 1..., ar]，其中 #cf_span[1 ≤ l ≤ r ≤ n]。对于每个正整数 #cf_span[s]，记 #cf_span[Ks] 为 #cf_span[s] 在该子数组中出现的次数。我们称该子数组的 _幂_ 为对所有正整数 #cf_span[s] 的乘积 #c...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions:**\n\nLet $ a = [a_1, a_2, \\dots, a_n] $ be an array of positive integers.  \nFor a subarray $ a[l:r] = [a_l, a_{l+1}, \\dots, a_r] $, define for each positive integer $ s $:  \n- $ K_s = \\#\\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments