Rt，数据太弱了，我莫队排序完全有问题900多ms卡过去了。。。（太弱轻喷）

---

亮点：（算块的时候算的是bool类型）

bool dir( int x )
{
	return ( x - 1 ) / len + 1;
}

---

---

---

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

#define N 200005
struct node
{
	int l, r;
	int id;
}ask[N];
int n, arr[N], len, lx[N], rx[N], q, ans[N], sum, cnt[N];

bool dir( int x )
{
	return ( x - 1 ) / len + 1;
}
bool cmp( node s1, node s2 )
{
	return dir(s1.l) == dir(s2.l) ? s1.r < s2.r : dir(s1.l) < dir(s2.l);//保证左端点和右端点至少有一个在同一个块内
}
void add( int x )
{
	sum += 1 + 2 * cnt[arr[x]];
	cnt[arr[x]] ++;
}
void del( int x )
{
	sum -= 2 * cnt[arr[x]] - 1;
	cnt[arr[x]] --;
}
int main()
{
	int k = 0;
	scanf( "%d %d %d", &n, &q, &k );
	len = sqrt( n );
	for ( int i = 1; i <= n; i ++ )
	{
		scanf( "%d", &arr[i] );
	}
	for ( int i = 1; i <= q; i ++ )
	{
		scanf( "%d %d", &ask[i].l, &ask[i].r );
		ask[i].id = i;
	}
	sort( ask+1, ask+1+q, cmp );
	int l = 1, r = 0;
	for ( int i = 1; i <= q; i ++ )
	{
		while( l > ask[i].l )
		{
			add( --l );
		}
		while( r < ask[i].r )
		{
			add( ++r );
		}
		while( l < ask[i].l )
		{
			del( l++ );
		}
		while( r > ask[i].r )
		{
			del( r-- );//注意，因为这个值也是要被删除的，所以先减！！
		}
		ans[ask[i].id] = sum;
	}
	for ( int i = 1; i <= q; i ++ )
	{
		printf( "%d\n", ans[i] );
	}
	return 0;
}