CF 86D 莫隊（卡常數）

D. Powerful array

time limit per test

5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

An array of positive integers a1, a2, ..., an is given. Let us consider its arbitrary subarray al, al + 1..., ar, where 1 ≤ l ≤ r ≤ n. For every positive integer s denote by Ks the number of occurrences of s into the subarray. We call the power of the subarray the sum of products Ks·Ks·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 ai (1 ≤ ai ≤ 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).

Examples

3 2
1 2 1
1 2
1 3      

3
6      

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

20
20
20      

Note

Consider the following array (see the second sample) and its [2, 7] subarray (elements of the subarray are colored):

Then K1 = 3, K2 = 2, K3 = 1, so the power is equal to 32·1 + 22·2 + 12·3 = 20.

題意： 

一個數列，問[L,R]區間内（每個數字的個數的平方*數字的大小）的和。 

思路： 

莫隊模闆。 

離線+分塊

将n個數分成sqrt(n)塊。

對所有詢問進行排序，排序标準：

      1. Q[i].left /block_size < Q[j].left / block_size （塊号優先排序）

      2. 如果1相同，則 Q[i].right < Q[j].right （按照查詢的右邊界排序）

問題求解：

從上一個查詢後的結果推出目前查詢的結果。（這個看程式中query的部分）

如果一個數已經出現了x次，那麼需要累加(2*x+1)*a[i]，因為(x+1)^2*a[i] = (x^2 +2*x + 1)*a[i]，x^2*a[i]是出現x次的結果，(x+1)^2 * a[i]是出現x+1次的結果。

時間複雜度分析：

排完序後，對于相鄰的兩個查詢，left值之間的差最大為sqrt(n)，則相鄰兩個查詢左端點移動的次數<=sqrt(n)，總共有t個查詢，則複雜度為O(t*sqrt(n))。

又對于相同塊内的查詢，right端點單調上升，每一塊所有操作，右端點最多移動O(n)次，總塊數位sqrt(n)，則複雜度為O(sqrt(n)*n)。

right和left的複雜度是獨立的，是以總的時間複雜度為O(t*sqrt(n)  +  n*sqrt(n))。

1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <cmath>
 6 using namespace std;
 7 #define N 200100
 8 typedef long long ll;
 9 ll a[N], cnt[N*5], ans[N], res;
10 int L, R;
11 
12 struct node {
13     int x, y, l, p;
14 } q[N];
15 bool cmp(const node &x, const node &y) {
16     if (x.l == y.l) return x.y < y.y;
17     return x.l < y.l;
18 }
19 void query(int x, int y, int flag) {
20     if (flag) {
21         for (int i=x; i<L; i++) {
22             res += ((cnt[a[i]]<<1)+1)*a[i];
23             cnt[a[i]]++;
24         }
25         for (int i=L; i<x; i++) {
26             cnt[a[i]]--;
27             res -= ((cnt[a[i]]<<1)+1)*a[i];
28         }
29         for (int i=y+1; i<=R; i++) {
30             cnt[a[i]]--;
31             res -= ((cnt[a[i]]<<1)+1)*a[i];
32         }
33         for (int i=R+1; i<=y; i++) {
34             res += ((cnt[a[i]]<<1)+1)*a[i];
35             cnt[a[i]]++;
36         }
37 
38     } else {
39         for (int i=x; i<=y; i++) {
40             res += ((cnt[a[i]]<<1)+1)*a[i];
41             cnt[a[i]]++;
42         }
43     }
44     L = x, R = y;
45 }
46 int main() {
47     int n, t;
48 
49     scanf("%d%d", &n, &t);
50     for (int i=1; i<=n; i++) scanf("%I64d", &a[i]);
51     int block_size = sqrt(n);
52 
53     for (int i=0; i<t; i++) {
54         scanf("%d%d", &q[i].x, &q[i].y);
55         q[i].l = q[i].x / block_size;
56         q[i].p = i;
57     }
58 
59     sort(q, q+t, cmp);
60 
61 
62     memset(cnt, 0, sizeof(cnt));
63 
64     res = 0;
65     for (int i=0; i<t; i++) {
66         query(q[i].x, q[i].y, i);
67         ans[q[i].p] = res;
68     }
69 
70     for (int i=0; i<t; i++) printf("%I64d\n", ans[i]);
71 
72     return 0;
73 }      

我的旨在學過的東西不再忘記（主要使用艾賓浩斯遺忘曲線算法及其它智能學習複習算法）的偏公益性質的完全免費的程式設計視訊學習網站：

fanrenyi.com；有各種前端、後端、算法、大資料、人工智能等課程。

版權申明：歡迎轉載，但請注明出處

一些博文中有一些參考内容因時間久遠找不到來源了沒有注明，如果侵權請聯系我删除。

部落客25歲，前端後端算法大資料人工智能都有興趣。

大家有啥都可以加部落客聯系方式（qq404006308，微信fan404006308）互相交流。工作、生活、心境，可以互相啟迪。

聊技術，交朋友，修心境，qq404006308，微信fan404006308

26歲，真心找女朋友，非誠勿擾，微信fan404006308，qq404006308

人工智能群：939687837

作者相關推薦

感悟總結

其它重要感悟總結

感悟總結200813

最近心境200830

最近心境201019

201218-210205