@[wpy233](/user/214172)
```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read()
{
char ch;
ll x=0,f=1;
for(;!isdigit(ch);ch=getchar())
if(ch=='-')
f=-1;
for(; isdigit(ch);ch=getchar())
x*=10,x+=(ch-'0');
return x*f;
}
int n,sq;
int a[50005];
int Q,k;
struct QAQ{
int l;
int r;
int id;
}q[50005];
bool comp(QAQ x,QAQ y)
{
int xl=x.l/sq,yl=x.l/sq;
if(xl!=yl) return xl<yl;
return x.r<y.r;
}
ll cnt[50005],cur,l=1,r;
ll ans[50005];
inline void add(int p)
{
cur+=(2*cnt[a[p]]+1);
cnt[a[p]]++;
}
inline void del(int p)
{
cnt[a[p]]--;
cur-=(2*cnt[a[p]]+1);
}
int main()
{
n=read();
Q=read();
k=read();
sq=pow(n, 0.667);
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=Q;i++)
{
q[i].l=read();
q[i].r=read();
q[i].id=i;
}
sort(q+1,q+Q+1,comp);
for(int i=1;i<=Q;i++)
{
while(l>q[i].l) add(--l);
while(r<q[i].r) add(++r);
while(l<q[i].l) del(l++);
while(r>q[i].r) del(r--);
ans[q[i].id]=cur;
}
for(int i=1;i<=Q;i++)
printf("%lld\n",ans[i]);
return 0;
}
```
by juruoCms @ 2023-01-16 12:07:12
改了一下排序和块长
by CmsMartin @ 2023-01-16 12:08:05
@[juruoCms](/user/431577) 谢谢，已经过题了
Orz %%%
by wpy233 @ 2023-01-16 12:10:53
@[CmsMartin](/user/461426) 谢谢，学到了
by wpy233 @ 2023-01-16 12:11:49