Powerful array CodeForces - 86D（莫队）

给你n个数，m次询问，Ks为区间内s的数目，求区间[L,R]之间所有Ks*Ks*s的和。1<=n，m<=200000.1<=s<=10^6

#include <iostream>

#include <cstdio>

#include <sstream>

#include <cstring>

#include <map>

#include <set>

#include <vector>

#include <stack>

#include <queue>

#include <algorithm>

#include <cmath>

#define MOD 2018

#define LL long long

#define ULL unsigned long long

#define Pair pair<int, int>

#define mem(a, b) memset(a, b, sizeof(a))

#define _  ios_base::sync_with_stdio(0),cin.tie(0)

//freopen("1.txt", "r", stdin);

using namespace std;

const int maxn = , INF = 0x7fffffff;

int n, m, pos[maxn], s[maxn*], c[maxn];

LL ans;

struct node

{

    int l, r, id;

    LL res;

}Node[maxn];

bool cmp(node a, node b)

{

    return pos[a.l] == pos[b.l] ? (a.r < b.r) : (a.l < b.l);

}

bool cmp_id(node a, node b)

{

    return a.id < b.id;

}

void add(LL x)

{

    s[c[x]]++;

    ans += c[x]*(s[c[x]]*s[c[x]] - (s[c[x]]-)*(s[c[x]]-));

}

void del(LL x)

{

    s[c[x]]--;

    ans -= c[x]*((s[c[x]]+)*(s[c[x]]+) - (s[c[x]])*(s[c[x]]));

}

int main()

{

    ans = ;

    scanf("%d%d", &n, &m);

    for(int i=; i<=n; i++)

        scanf("%d", &c[i]);

    int block = sqrt(n);

    for(int i=; i<=n; i++)

        pos[i] = (i-)/block + ;

    for(int i=; i<=m; i++)

    {

        scanf("%d%d", &Node[i].l, &Node[i].r);

        Node[i].id = i;

    }

    sort(Node+, Node++m, cmp);

    for(int i=, l=, r=; i<=m; i++)

    {

        for(; r < Node[i].r; r++)

            add(r+);

        for(; r > Node[i].r; r--)

            del(r);

        for(; l < Node[i].l; l++)

            del(l);

        for(; l > Node[i].l; l--)

            add(l-);

        Node[i].res = ans;

    }

    sort(Node+, Node++m, cmp_id);

    for(int i=; i<=m; i++)

        printf("%I64d\n", Node[i].res);

    return ;

}