Yandex.Algorithm 2011 Round 2-D - Powerful array-莫隊算法（分塊算法）

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

莫隊算法就是處理這類能O1從區間【l,r】得到 【l-1，r】【l,r+1】，不帶修改的區間查詢的一類問題。

題目要求任意 subarray 的 cnt[a[i]]*cnt[a[i]]*a[i]

按照套路，把所有區間按 左端點 所在塊作第一關鍵字，右端點第二關鍵字 排序

周遊，預處理第一次詢問後，每次詢問暴力求解，轉移如下：

  res -= cnt[a[i]]*cnt[a[i]]*a[i];

            cnt[a[i]]++;

            res += cnt[a[i]]*cnt[a[i]]*a[i];

算法複雜度為q*sqrt n 

考慮右指針，先是按照遞增順序移動，假設目前塊右指針在最右端，當下一塊時，需移動到最左端，那麼也就是每跨越一個塊，最多移動O(N)，總共sqrtn個塊，複雜度n*sqrtn

考慮左指針如果在同一塊,移動量不超過sqrtn【在一塊内嘛】

如果是跨越一塊，移動量最多不超過2*sqrtn【塊長隻有sqrtn】

複雜度（q*sqrtn）

總複雜度（q+n）*sqrtn

----------------------------------------------------------

有一點 add move 的時候直接那剛才的暴力轉移會逾時，

因為每次變化隻有1， 也就是 x*x*a 變成 （x+1）*（x+1）*a，顯然我們直接加上 a*（2*x+1）就好了。。。最後跑了 1.9S

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iostream>
using namespace std;
#define N 200100
typedef long long ll;
int a[N], cnt[N*5];
ll  ans[N], res;
int L, R;

struct node
{
    int x, y, l, p;
} q[N];
bool cmp(const node &x, const node &y)
{
    if (x.l == y.l) return x.y < y.y;
    return x.l < y.l;
}
void query(int x, int y, int flag)
{
    if (flag)
    {
        for (int i=x; i<L; i++)
        {
            res += (cnt[a[i]]*2+1)*a[i];
            cnt[a[i]]++;
        }
        for (int i=L; i<x; i++)
        {
            res += (-cnt[a[i]]*2+1)*a[i];
            cnt[a[i]]--;
        }
        for (int i=y+1; i<=R; i++)
        {
            res += (-cnt[a[i]]*2+1)*a[i];
            cnt[a[i]]--;
        }
        for (int i=R+1; i<=y; i++)
        {
            res += (cnt[a[i]]*2+1)*a[i];
            cnt[a[i]]++;
        }

    }
    else
    {

        for (int i=x; i<=y; i++)
        {
            res += (cnt[a[i]]*2+1)*a[i];
            cnt[a[i]]++;
        }
    }
    L = x, R = y;
}
int main()
{
    int n, t;

    scanf("%d%d", &n, &t);
    for (int i=1; i<=n; i++) scanf("%d", &a[i]);
    int block_size = sqrt(1.0*n);

    for (int i=0; i<t; i++)
    {
        scanf("%d%d", &q[i].x, &q[i].y);
        q[i].l = q[i].x / block_size;
        q[i].p = i;
    }
    sort(q, q+t, cmp);

    res = 0;
    for (int i=0; i<t; i++)
    {
        query(q[i].x, q[i].y, i);
        ans[q[i].p] = res;
    }

    for (int i=0; i<t; i++) printf("%I64d\n", ans[i]);

    return 0;
}