莫队板子。
//P2709 小B的询问
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=50005;
struct Query
{
int l,r,id;
}q[MAXN];
int n,m,k,t,num,cnt[MAXN],belong[MAXN],a[MAXN];
ll ans[MAXN],now;
bool cmp(Query a,Query b)
{
return (belong[a.l]^belong[b.l])?belong[a.l]<belong[b.l]:((belong[a.l]&1)?a.r<b.r:a.r>b.r);
}
void add(int x)
{
now+=cnt[x]*2+1;
cnt[x]++;
return;
}
void del(int x)
{
now-=cnt[x]*2-1;
cnt[x]--;
return;
}
int main()
{
int l=1,r=0,ql,qr;
scanf("%d%d%d",&n,&m,&k);
t=sqrt(n);
num=ceil(n*1.0/t);
for(int i=1;i<=num;i++)
{
for(int j=(i-1)*t+1;j<=i*t;j++)
{
belong[j]=i;
}
}
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&q[i].l,&q[i].r);
q[i].id=i;
}
sort(&q[1],&q[m+1],cmp);
for(int i=1;i<=m;i++)
{
ql=q[i].l;
qr=q[i].r;
while(l<ql)
{
del(a[l++]);
}
while(l>ql)
{
add(a[--l]);
}
while(r<qr)
{
add(a[++r]);
}
while(r>qr)
{
del(a[r--]);
}
ans[q[i].id]=now;
}
for(int i=1;i<=m;i++)
{
printf("%d\n",ans[i]);
}
return 0;
}
/*
* 洛谷
* https://www.luogu.com.cn/problem/P2709
* C++20 -O0
* 2022.10.1
*/