这题没人用分块吧？
好像分块比较麻烦，但是我太弱了，不会莫队，就打了一个比较巧妙的分块。
1.build函数。
还是像普通分块一样的写，只是我们需要预处理两个数组。
(f[i][j])表示从开始到第(i)块，颜色为(j)的颜色有多少个（前缀和）。
这个东西很好处理。
for (int i=1;i<=num;i++) {
for (int j=1;j<=n;j++)
f[i][a[j]]=f[i-1][a[j]];
for (int j=l[i];j<=r[i];j++)
f[i][a[j]]++;
}
(s[i][j])表示第(i)块，到第(j)块的贡献。
换句话说，就是第i块到第j块之间的答案。也比较好处理。
假设现在已经处理到了(s[i][j-1]),那么(s[i][j])中的颜色(k)，每出现一次，就用一个(tmp[j])数组自加，
最后假设(s[i][j-1])中颜色k出现次数为(x)，那么$$x=f[j-1][k]-f[i-1][k]$$
(s[i][j])中颜色k出现次数就是(x+tmp[k]).
那么我们就让$$s[i][j]+=2*(x+tmp[k])+1$$
为什么呢？例如(tmp[k]=1)时，$$(x+1){x+1}-x2=2×x+1$$
还要注意一个问题，(tmp)数组要清零，当然不能单纯地使用(memset)（会超时），而是重复一次上面的循环，将它清零。
for (int i=1;i<=num;i++)
for (int j=i;j<=num;j++) {
s[i][j]=s[i][j-1];
for (int k=l[j];k<=r[j];k++) {
int p=f[j-1][a[k]]-f[i-1][a[k]];
s[i][j]+=2*(p+tmp[a[k]])+1;
tmp[a[k]]++;
}
for (int k=l[j];k<=r[j];k++)
tmp[a[k]]=0;
}
2.总的代码就是下面这样，很好理解：
#include <bits/stdc++.h>
using namespace std;
const int N=50010,S=250;
int n,m,q,a[N],s[S][S];
int f[S][N],block,num;
int belong[N],l[S],r[S],tmp[N];
void build()
{
block=sqrt(n);
num=n/block;
if (n%block) num++;
for (int i=1;i<=num;i++)
l[i]=(i-1)*block+1,r[i]=i*block;
r[num]=n;
for (int i=1;i<=n;i++)
belong[i]=(i-1)/block+1;
for (int i=1;i<=num;i++) {
for (int j=1;j<=n;j++)
f[i][a[j]]=f[i-1][a[j]];
for (int j=l[i];j<=r[i];j++)
f[i][a[j]]++;
}
for (int i=1;i<=num;i++)
for (int j=i;j<=num;j++) {
s[i][j]=s[i][j-1];
for (int k=l[j];k<=r[j];k++) {
int p=f[j-1][a[k]]-f[i-1][a[k]];
s[i][j]+=2*(p+tmp[a[k]])+1;
tmp[a[k]]++;
}
for (int k=l[j];k<=r[j];k++)
tmp[a[k]]=0;
}
}
long long ask(int ls,int rs)
{
long long ans=0;
if (belong[ls]==belong[rs]) {
for (int i=ls;i<=rs;i++) {
ans+=2*tmp[a[i]]+1;
tmp[a[i]]++;
}
for (int i=ls;i<=rs;i++) tmp[a[i]]=0;
return ans;
}
for (int i=ls;i<=r[belong[ls]];i++) {
int p=f[belong[rs]-1][a[i]]-f[belong[ls]][a[i]];
ans+=2*(p+tmp[a[i]])+1;
tmp[a[i]]++;
}
for (int i=l[belong[rs]];i<=rs;i++) {
int p=f[belong[rs]-1][a[i]]-f[belong[ls]][a[i]];
ans+=2*(p+tmp[a[i]])+1;
tmp[a[i]]++;
}
for (int i=ls;i<=r[belong[ls]];i++) tmp[a[i]]=0;
for (int i=l[belong[rs]];i<=rs;i++) tmp[a[i]]=0;
if (belong[ls]+1==belong[rs]) return ans;
return ans+s[belong[ls]+1][belong[rs]-1];
}
int main()
{
ios::sync_with_stdio(0);
cin>>n>>m>>q;
for (int i=1;i<=n;i++)
cin>>a[i];
build();
while (m--) {
int ls,rs;
cin>>ls>>rs;
cout<<ask(ls,rs)<<endl;
}
return 0;
}