Code

#include <cmath>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

int n, m, k, maxb, b[50007];

ll sum, cnt[50007], ans1[50007];

struct Query
{
	int l, r, id, pos;
	bool operator <(const Query &x) const
	{
		if (pos == x.pos) return r < x.r;
    	else return pos < x.pos;
	}
} a[50007];

void add(int i)
{
	sum += 2 * cnt[i] - 1;
	cnt[i]++;
}

void del(int i)
{
	cnt[i]--;
	sum -= 2 * cnt[i] + 1;
}

int main()
{
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
	maxb = (int) n / sqrt(m);
	for (int i = 1; i <= m; ++i)
	{
		scanf("%d%d", &a[i].l, &a[i].r);
		a[i].id = i, a[i].pos = (a[i].l - 1) / maxb + 1;
	}
	sort(a + 1, a + 1 + m);
	for (int i = 1, l = 1, r = 0; i <= m; ++i)
	{
		while (l < a[i].l) del(b[l++]);
		while (l > a[i].l) add(b[--l]);
		while (r < a[i].r) add(b[r++]);
		while (r > a[i].r) del(b[--r]);
		ans1[a[i].id] = sum;
	}
	for (int i = 1; i <= m; ++i) printf("%lld\n", ans1[i]);
	return 0;
}

本Code样例输出

-4
-7
-7
-12