codeforces86D 莫隊算法

題目連結：http://codeforces.com/problemset/problem/86/D

題目大意：給你n個數，m次詢問，Ks為區間内s的數目，求區間[L,R]之間所有Ks*Ks*s的和。1<=n，m<=200000.1<=s<=10^6

思路：直接用莫隊算法，前面的博文講過原理。這裡再說一下增加和删除操作。因為要求Ks*Ks*s，是以每次增加一個需要在原有結果上加（Ks*Ks*x - (Ks-1)*(Ks-1)*x),删除的話也是要相應的減去。

莫隊算法還是很好用的。

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <iomanip>

using namespace std;
//#pragma comment(linker, "/STACK:102400000,102400000")
#define maxn 200050
#define MOD 1000000007
#define mem(a , b) memset(a , b , sizeof(a))
#define LL long long
#define ULL unsigned long long
#define FOR(i , n) for(int i = 1 ;  i<= n ; i ++)
typedef pair<int , int> pii;
const long long INF= 0x3fffffff;

int n , m;
int a[maxn],pos[maxn],vis[maxn*10] ;
LL ans[maxn],num;
struct node
{
    int l , r , id;
}q[maxn];

bool cmp(node n1 , node n2)
{
    if(pos[n1.l] == pos[n2.l])
        return n1.r < n2.r;
    return pos[n1.l] < pos[n2.l];
}

void add(LL x)
{
    vis[x]++;
    num += x*(vis[x]*vis[x] - (vis[x]-1)*(vis[x]-1));
}

void del(LL x)
{
    vis[x]--;
    num -= x*((vis[x]+1)*(vis[x]+1) - (vis[x])*(vis[x]));
}

int main()
{
    while(scanf("%d %d" , &n , &m) != EOF)
    {
        mem(vis , 0);mem(ans , 0);
        double dis = sqrt(1.0*n);
        for(int i = 1 ; i <= n ;i ++)
        {
            scanf("%d" , &a[i]);
            pos[i] = i/dis;
        }
        for(int i = 1 ; i <= m ; i ++)
        {
            scanf("%d %d" , &q[i].l , &q[i].r);
            q[i].id = i;
        }
        sort(q+1 , q +1 + m , cmp);
        num = 0;
        int l = 1 , r = 0;
       // cout << "YES" << endl;
        for(int i = 1 ; i <= m ; i ++)
        {
            while(r < q[i].r) add(a[++r]);
            while(r > q[i].r) del(a[r--]);
            while(l < q[i].l) del(a[l++]);
            while(l > q[i].l) add(a[--l]);
            ans[q[i].id] = num;
        }
        for(int i = 1 ; i <= m ; i ++)
            printf("%I64d\n" , ans[i]);
    }
    return 0;
}