本人一个刚刚学莫队的蒟蒻，这题的$k$输不输入有什么用，不输入都能过（不是题出错了，是测试数据太水了），但只要$k$小一点整个代码都不会过，本人假$AC$代码放在下面了，整个代码只是把$k$输入进来了，根本没用上$k$.

#include <bits/stdc++.h>
using namespace std;
const int N = 50005;
typedef long long ll;
struct node
{
	int l , r , id;
}q[N];
int n , m , k , a[N] , blk , cnt[N];
ll ans , res[N];
bool cmp (node x , node y)
{
	if((x.r / blk) == (y.r / blk)) return x.l < y.l;
	else return x.r < y.r;
}

void add(int x) 
{
	ans -= 1ll * cnt[a[x]] * cnt[a[x]];
	cnt[a[x]]++;
	ans += 1ll * cnt[a[x]] * cnt[a[x]];
}
void del(int x) 
{
	ans -= 1ll * cnt[a[x]] * cnt[a[x]];
	cnt[a[x]]--;
	ans += 1ll * cnt[a[x]] * cnt[a[x]];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> k;
	blk = sqrt(n);
	for(int i = 1 ; i <= n ; i++) cin >> a[i];
	for(int i = 1 ; i <= m ; i++) 
	{
		cin >> q[i].l >> q[i].r;
		q[i].id = i;
	}
	sort(q + 1 , q + 1 + m , cmp);
	for(int i = 1 , l = 1 , r = 0 ; i <= m ; i++)
	{
		int ql = q[i].l , qr = q[i].r;
		while(l < ql) del(l++);
		while(l > ql) add(--l);
		while(r > qr) del(r--);
		while(r < qr) add(++r);
		res[q[i].id] = ans;
	}
	for(int i = 1 ; i <= m ; i++) cout << res[i] << endl;
	return 0;
}