题目大意：给定一个序列，多次询问某个区间内所有数字出现个数的平方和。

莫队算法的题目。

所谓莫队算法，指的是以下一类问题：

已知$[L,R]$的解，能算出$[L,R+1],[L,R-1],[L+1,R],[L-1,R]$的解的，就可以使用莫队算法。莫队算法就是离线询问，排序后处理，其实就是大暴力~优化了顺序。

然后就打了遍莫队，发现TLE了。。。

然后去看了$PoPoQQQ$大神的代码，发现了这样一个奇怪的东西：

bool operator < (const quest &Y) const {
	if((Y.l>>8)!=(l>>8)) return l<Y.l;
	else return r<Y.r;
}

为什么要除以256...？不理解。。

发现我自己死活过不去，于是改成了一样的写法，竟然，过了。。。900ms。

我想知道这到底是个什么优化。。于是就把>>8改成了>>3，发现，也过了，但是，明显慢。

（RunID，User，Languege隐藏）

上面那行是>>3的，下面那行是>>8的，这时间的差别。。。

upd: 2015/08/28 19:51

问了聚聚之后终于知道了。。。我的过。。

莫队算法的排序是左端点在一定区间内，按照右端点排序。。。

不是双关键字快排。。

一定区间这里取256为一个区间，一般取$sqrt(n)$。

我果然是弱= =$tooyoungtoosimple$

============================================

代码时间：

#include<stdio.h>
#include<algorithm>
using namespace std;
struct quest{
	int l,r,id;
	bool operator < (const quest &Y) const {
		if((Y.l>>8)!=(l>>8)) return l<Y.l;
		else return r<Y.r;
	}
}q[50010];
int n,m,k,a[50010];
int cnt[50010],left=1,right=0;
unsigned int ans[50010],ansx=0;
inline void g(int x,int t) {
	ansx-=cnt[x]*cnt[x];
	cnt[x]+=t;
	ansx+=cnt[x]*cnt[x];
}
int main() {
	scanf("%d%d%d",&n,&m,&k);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	for (int i=1;i<=m;++i) q[i].id=i,scanf("%d%d",&q[i].l,&q[i].r);
	sort(q+1,q+m+1);
	for (int i=1;i<=m;++i) {
		while(right<q[i].r) g(a[++right],1);
		while(left>q[i].l) g(a[--left],1);
		while(right>q[i].r) g(a[right--],-1);
		while(left<q[i].l) g(a[left++],-1);
		ans[q[i].id]=ansx;
	}
	for (int i=1;i<=m;++i) printf("%u\n",ans[i]);
	return 0;
}