NBUT1457

不知道哪里的oj。。做了交不上去。。

也是莫队的模板题

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

#define MAXN 100005

#define ll long long

struct Query{

    int L,R,id;

}q[MAXN];

ll ans[MAXN],cnt[MAXN];//这个颜色在当前区间出现的次数

int s,note[MAXN];

bool cmp(Query a,Query b){

    if(a.L/s == b.L/s) return a.R<b.R;

    return a.L/s < b.L/s;

}

ll cube(ll a){

    return a*a*a;

}

int main(){

    int n,m;

    scanf("%d",&n);

    s=(int)sqrt(n);

    for(int i=;i<=n;i++) scanf("%d",&note[i]);

    scanf("%d",&m);

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

        int a,b;

        scanf("%d%d",&a,&b);

        q[i]=(Query){a,b,i};

    }

    sort(q,q+m,cmp);

    int L=,R=;

    ll res=;

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

        while(R<q[i].R){

            R++;

            res+=cube((cnt[note[R]]+))-cube(cnt[note[R]]);

            cnt[note[R]]++;

        }

        while(R>q[i].R){

            res-=cube(cnt[note[R]])-cube(cnt[note[R]]-);

            cnt[note[R]]--;

            R--;

        }

        while(L<q[i].L){

            res-=cube(cnt[note[L]])-cube(cnt[note[L]]-);

            cnt[note[L]]--;

            L++;

        }

        while(L>q[i].L){

            L--;

            res+=cube(cnt[note[L]]+)-cube(cnt[note[L]]);

            cnt[note[L]]++;

        }

        ans[q[i].id]=res;

    }

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

        printf("%d\n", ans[i]);

    }

    return ;

}