luogu P2709 小B的询问 分块+莫队

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N],belong[N];
int n,q,k;
inline int read()
{
    int k=0;
    char c;
    c=getchar();
    while(!isdigit(c))c=getchar();
    while(isdigit(c))
    {
        k=(k<<3)+(k<<1)+c-‘0‘;
        c=getchar();
    }
    return k;
}
struct node
{
    int l,r;
    int id;
} e[N];
int cnt[N];
int Ans;
int ans[N];
inline bool cmp(node a,node b)
{
    if(belong[a.l]==belong[b.l])
        return belong[a.r]<belong[b.r];
    return belong[a.l]<belong[b.l];
}
inline void add(int x)
{
    Ans-=cnt[a[x]]*cnt[a[x]];
    ++ cnt[a[x]];
    Ans+=cnt[a[x]]*cnt[a[x]];
}
inline void del(int x)
{
    Ans-=cnt[a[x]]*cnt[a[x]];
    -- cnt[a[x]];
    Ans+=cnt[a[x]]*cnt[a[x]];
}
int main()
{
    n=read(),q=read(),k=read();
    int block = pow(n,0.5);
    for(register int i = 1; i <= n; ++ i)
    {
        a[i]=read();
        belong[i] = (i - 1) / block + 1;
    }
    for(register int i=1; i<=q; i++)
    {
        e[i].l=read();
        e[i].r=read();
        e[i].id=i;
    }
    sort(e+1,e+1+q,cmp);
    int l = 1,r = 0;
    for(register int i = 1; i <= q; ++ i)
    {
        while(l < e[i].l)
            del(l ++);
        while(l > e[i].l)
            add(-- l);
        while(r < e[i].r)
            add(++ r);
        while(r > e[i].r)
            del(r --);
        ans[e[i].id] = Ans;
    }
    for(register int i = 1; i <= q; ++ i)
        cout<<ans[i]<<endl;
    return 0;
}