蒟蒻本来想给莫队加个优化，结果越弄越糟。。。
本意是如果 （两个区间不相交） 或者 （不存在要求的区间包含当前的区间 且 暴力的代价更少），那就用暴力。
结果发现初始化桶特别耗时，效率更慢。
然后就把这份跑得贼慢的代码交了上去，居然过了。

#include <bits/stdc++.h>
using namespace std;
int n, m, k, b, now;
int l1, r1, l2, r2;
int A[50005];
int t[50005];
int ans[50005];
struct RANGE{
	int l, r, v;
}range[50005];
int cmp(struct RANGE x, struct RANGE y)
{
	if(x.l / b == y.l / b) return x.r < y.r;
	else return x.l / b < y.l / b;
}
void add(int x)
{
	now += 2 * t[x] + 1;
	t[x]++;
}
void del(int x)
{
	now -= 2 * t[x] - 1;
	t[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++) scanf("%d%d", &range[i].l, &range[i].r), range[i].v = i;
	b = int(sqrt(n)), l1 = 1, r1 = 0;
	sort(range+1, range+m+1, cmp);
	for(int i=1; i<=m; i++){
		l2 = range[i].l, r2 = range[i].r;
		if(l1 > r2 || r1 < l2 || !(l1 >= l2 && r1 <= r2) && abs(l1-l2) + abs(r1 - r2) > r2 - l2 + 1){
			l1 = l2, r1 = l2 - 1;
			now = 0;
			for(int j=1; j<=k; j++) t[j] = 0;
		}
		while(l1 < l2) del(A[l1]), l1++;
		while(r1 > r2) del(A[r1]), r1--;
		while(l1 > l2) l1--, add(A[l1]);
		while(r1 < r2) r1++, add(A[r1]);
		ans[range[i].v] = now;
	}
	for(int i=1; i<=m; i++) printf("%d\n", ans[i]);
	return 0;
}

是数据太水了吗？