小B有一个序列，包含N个1~K之间的整数。他一共有M个询问，每个询问给定一个区间[L..R]，求Sigma(c(i)^2)的值,其中i的值从1到K，其中c(i)表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。
可是使用莫队算法，我们移动的时候，计算贡献即可，那么如何计算贡献呢？？
我们知道对于cnt[i]^2 ，也就数字i对应现在的值是cnt[i]^2，那么如果当前点的答案是如此的，我们现在要吧cnt[i]+1，那么如何加上去呢？
简单的方法就是让答案加上(cnt[i]+1)^2-(cnt[i])^2，其实吧式子展开就是贡献加上2cnt[i]+1。减法也是一样，但是需要注意的是贡献减去2*cnt[i]-1，列一下式子就知道了
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxx = 1e5+;
int block;
int res;
int a[maxx];
LL vis[maxx];
LL ans[maxx];
struct node{
int l,r;
int id;
friend bool operator < (node &a,node &b){
if (a.l/block==b.l/block){
return a.r<b.r;
}
return a.l/block<b.l/block;
}
}q[maxx];
void add(int x){
res+=(*vis[a[x]]+);
vis[a[x]]++;
}
void del(int x){
res-=(*vis[a[x]]-);
vis[a[x]]--;
}
int main(){
int n,m,k;
int l,r;
while(~scanf("%d%d%d",&n,&m,&k)){
memset(vis,,sizeof(vis));
res=;
block=sqrt(n);
for (int i=;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=;i<=m;i++){
scanf("%d%d",&q[i].l,&q[i].r);
q[i].id=i;
}
sort(q+,q++m);
int l=,r=;
for (int i=;i<=m;i++){
while(l<q[i].l){
del(l);
l++;
}
while(l>q[i].l){
l--;
add(l);
}
while(r<q[i].r){
r++;
add(r);
}
while(r>q[i].r){
del(r);
r--;
}
ans[q[i].id]=res;
}
for (int i=;i<=m;i++){
printf("%lld\n",ans[i]);
}
}
return ;
}