BZOJ 3781 莫队

思路：不能再裸的裸题……

//By SiriusRen
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 55555
int n,m,k,a[N],s[N],pos[N],ans;
struct Ask{int l,r,ans,id;}ask[N];
bool cmp(Ask a,Ask b){
    if(pos[a.l]==pos[b.l])return a.r<b.r;
    return a.l<b.l;
}
bool cmp2(Ask a,Ask b){return a.id<b.id;}
void update(int num,int wei){
    ans-=s[num]*s[num];
    s[num]+=wei;
    ans+=s[num]*s[num];
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=m;ask[i].id=i,i++)
        scanf("%d%d",&ask[i].l,&ask[i].r);
    int block=sqrt(n);
    for(int i=1;i<=n;i++)pos[i]=(i-1)/block+1;
    sort(ask+1,ask+1+m,cmp);
    for(int i=1,l=1,r=0;i<=m;i++){
        for(;r<ask[i].r;r++)update(a[r+1],1);
        for(;r>ask[i].r;r--)update(a[r],-1);
        for(;l<ask[i].l;l++)update(a[l],-1);
        for(;l>ask[i].l;l--)update(a[l-1],1);
        ask[i].ans=ans;
    }
    sort(ask+1,ask+1+m,cmp2);
    for(int i=1;i<=m;i++)
        printf("%d
",ask[i].ans);
}