D. Powerful array

https://codeforces.com/contest/86/problem/D

题意：n个数，m个查询。每个查询给出一个区间，查询的结果是区间内每个数出现次数的平方*该数的总和。

思路：莫队算法。分块，查询排序，输出。

总结：莫队算法适用于离线的情况，他的原理是将查询按左端点分块，块的大小是数量的开平方。然后对查询进行排序，块不同，按块id排序，在相同块内，按右端点升序排序。这种排序规则可以让右指针只往右边走。这里有一个非常重要的优化，就是在相邻的块内，右指针走到了最右边，此时为了避免右指针需要回溯到最左边，将下一个块按右端点降序排序！这点非常重要。 在这种左右指针的移动规则下，直接暴力查询即可!!太强了。

注意：块所在id，一定是按左端点排序。 相邻的块一定要有个波浪线的右指针移动优化。

摘抄一段介绍过来：
原文链接：https://blog.csdn.net/ACpartner/article/details/75998670
莫队算法主要是利用了曼哈顿距离的长度关系，将每一个询问的坐标抽象为一个点，然后将询问分块，进行排序（分块的原因是使得这些询问坐标的移动的曼哈顿距离达到 最小），排序之后再按照此时的顺序进行左右区间的移动，而在内部的实现的过程就要看各个题目的要求了，所以在这里主要是理解到，莫队算法的核心是：平面上移动曼哈顿距离最小 （利用分块求得平面上曼哈顿距离的最小生成树）+ 离线查询（无法在线查询），在解题的过程中也要想到使得每一次转移计算答案的时间也要是O（1）的，到此，莫队算法也就完成。

int BLOCK_SIZE;
struct queryNode{
    int l, r, id, block_id;
    long long ans;

    queryNode(){}

    queryNode(int l_, int r_, int id_):
        l(l_),
        r(r_),
        id(id_),
        block_id(l / BLOCK_SIZE)
        {}

};

void solve(){
    int n, m;
    cin >> n >> m;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
    }

    BLOCK_SIZE = sqrt(m);
    vector<queryNode> querys;
    for (int i = 1; i <= m; ++i){
        int l, r;
        cin >> l >> r;
        querys.emplace_back(l, r, i);
    }

    /*
      这个优化至关重要
    */
    sort(querys.begin(), querys.end(), [](const queryNode& a, const queryNode& b){
            return a.block_id != b.block_id ? a.block_id < b.block_id : a.block_id & 1 ? a.r < b.r : a.r > b.r;
         });
    int l = 1, r = 0;
    int s = *max_element(a.begin() + 1, a.end());
    vector<int> cnt(s + 1);
    long long ans = 0;
    auto cal = [&](int pos, int value){
        ans -= 1ll * cnt[pos] * cnt[pos] * pos;
        cnt[pos] += value;
        ans += 1ll * cnt[pos] * cnt[pos] * pos;
    };
    for (auto& q : querys){
        while (l < q.l) cal(a[l], -1), l ++;
        while (l > q.l) cal(a[l - 1],  1), l --;
        while (r > q.r) cal(a[r], -1), r --;
        while (r < q.r) cal(a[r + 1], 1), r++;
        q.ans = ans;
    }
    sort(querys.begin(), querys.end(), [](const queryNode& a, const queryNode& b){
            return a.id < b.id;
        });


    for (const auto& x : querys){
        cout << x.ans << '\n';
    }

}