莫队算法-Powerful array

谁借莪１个温暖的怀抱￠ 2021-11-22 20:30 270阅读 0赞

**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 *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).

Examples

input

Copy

3 2
    1 2 1
    1 2
    1 3

output

Copy

3
    6

input

Copy

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

output

Copy

20
    20
    20

Note

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

![bcfe4e39f9224efaaf47be30cadc378cab143929.png][]Then  *K*1 = 3, *K*2 = 2, *K*3 = 1, so the power is equal to 32·1 + 22·2 + 12·3 = 20.

题意大概是这样的，给出一个数组，对每次询问的区间进行计算，公式为数字出现次数的平方乘数字。

题意很好理解，主要问题是数据规模太大，数组大小和询问次数都是2e5。第一反应是前缀和，然后mle，试了一下分块，还是mle。补题的时候才看到莫队算法，学到了。

算法的大意是，对于密集的区间查询，可以尽可能利用已有的查询结果，修修补补凑合着用。

代码如下，内容参考[https://blog.csdn.net/vaeloverforever/article/details/82314626][https_blog.csdn.net_vaeloverforever_article_details_82314626]

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 2e5 + 50;
    const int INF = 0xffffff;
     
    int n,t;
    int arr[maxn];
    int cnt[1000005], id[maxn];
    ll ans[maxn];
    int L,R;
    int unit;
    ll now;
     
    struct range{
        int l,r;
        int askorder;
        friend bool operator < (const range &a, const range &b){
            return a.l/unit != b.l/unit ? a.l/unit < b.l/unit : a.r < b.r;    
        }
    }rangee[maxn];
     
    void del(int x){//删掉不在区间里的
        now -= ((cnt[arr[x]]<<1)-1)*(ll)arr[x];
            cnt[arr[x]]--;
    } 
    void add(int x){//加上进入区间的
        now += ((cnt[arr[x]]<<1)|1)*(ll)arr[x];
        cnt[arr[x]]++;
    }
     
    int main()
    {
        scanf("%d%d",&n,&t);
        for(int i = 1;i < n+1; ++i)
            scanf("%d",&arr[i]);
        unit = sqrt(t*2.0/3);//块大小
        for(int i = 0; i < t; ++i){
            scanf("%d%d",&rangee[i].l,&rangee[i].r);
            rangee[i].askorder = i;
        }
        sort(rangee, rangee+t);//排序以尽可能复用先前结果
        for(int i = 0; i < t; ++i){
            while (L < rangee[i].l) 
                del(L++);
            while (R > rangee[i].r) 
                del(R--);
            
            while (L > rangee[i].l) 
                add(--L);
            while (R < rangee[i].r) 
                add(++R);
            ans[rangee[i].askorder] = now;
        }
        for(int i = 0;i < t; ++i)
            printf("%lld\n",ans[i]);
        return 0;
    }

转载于:https://www.cnblogs.com/wengsy150943/p/11209823.html

[bcfe4e39f9224efaaf47be30cadc378cab143929.png]: /images/20211122/af3cbb2676ec4d65840f08e00dbfba64.png
[https_blog.csdn.net_vaeloverforever_article_details_82314626]: https://blog.csdn.net/vaeloverforever/article/details/82314626