题目描述
小B有一个序列，包含N个1~K之间的整数。他一共有M个询问，每个询问给定一个区间[L..R]，求Sigma(c(i)^2)的值,其中i的值从1到K，其中c(i)表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。
输入输出格式
输入格式：
第一行，三个整数N、M、K。
第二行，N个整数，表示小B的序列。
接下来的M行，每行两个整数L、R。
输出格式：
M行，每行一个整数，其中第i行的整数表示第i个询问的答案。
输入输出样例
说明
对于全部的数据，1<=N、M、K<=50000
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std; const int N=; int n,m,k;
int a[N],c[N];
int ans,Ans[N];
int belong[N];
struct Querry
{
int tim,l,r;
bool operator < (const Querry &a) const
{
if(belong[l]==belong[a.l]) return belong[r]<belong[a.r];
return belong[l]<belong[a.l];
}
}q[N]; int read()
{
char c=getchar();int num=;
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())
num=num*+c-'';
return num;
} void init()
{
n=read(),m=read(),k=read();
int size=sqrt(n);
for(int i=;i<=n;++i)
a[i]=read(),
belong[i]=(i-)/size+;
for(int i=;i<=m;++i)
q[i].l=read(),q[i].r=read(),q[i].tim=i;
sort(q+,q+m+); } /*void update(int now,bool type)
{
if(type)
{
ans-=c[now]*c[now];
++c[now];
ans+=c[now]*c[now];
}
else
{
ans-=c[now]*c[now];
--c[now];
ans+=c[now]*c[now];
}
}*/
void update(int now,bool type)
{
if(type)
ans+=c[now]<<|,++c[now]; //(a+1)*(a+1)==a*a+2*a+1，比a*a多了2*a+1
else
ans-=(c[now]<<)-,--c[now]; //(a-1)*(a-1)==a*a-2*a+1，比a*a少了2*a-1
} void work()
{
for(int i=q[].l;i<=q[].r;++i)
update(a[i],);
Ans[q[].tim]=ans;
for(int i=;i<=m;++i)
{
if(q[i].l>q[i-].l)
for(int j=q[i-].l;j<q[i].l;++j)
update(a[j],);
if(q[i].l<q[i-].l)
for(int j=q[i].l;j<q[i-].l;++j)
update(a[j],);
if(q[i].r<q[i-].r)
for(int j=q[i].r+;j<=q[i-].r;++j)
update(a[j],);
if(q[i].r>q[i-].r)
for(int j=q[i-].r+;j<=q[i].r;++j)
update(a[j],);
Ans[q[i].tim]=ans;
}
for(int i=;i<=m;++i)
printf("%d\n",Ans[i]);
} int main()
{
init();
work();
return ;
}