求调莫队板子

#include <bits/stdc++.h>
using namespace std;

const int N = 5e4 + 5;

int a[N], n, m, k, cnt[N], len, ans[N];

struct Node
{
	int id, l, r, p;
}q[N];

inline bool cmp(register const Node &a, register const Node &b)
{
	if (a.p != b.p) return a.p < b.p;
	return (a.p & 1 ? a.r < b.r : a.r > b.r);
}

inline void add(const int &x, int &res)
{
	res -= cnt[a[x]] * cnt[a[x]];
	cnt[a[x]]++;
	res += cnt[a[x]] * cnt[a[x]];
}

inline void del(const int &x, int &res)
{
	res -= cnt[a[x]] * cnt[a[x]];
	cnt[a[x]]--;
	res += cnt[a[x]] * cnt[a[x]];
}

int main()
{
	scanf("%d %d %d", &n, &m, &k);
	len = pow(n, 0.54);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 0; i < m; i++)
	{
		int l, r;
		scanf("%d %d", &l, &r);
		q[i] = { i, l, r, l / len };
	}
	sort(q, q + m, cmp);
	int nl = 1, nr = 0;
	for (int i = 0; i < m; i++)
	{
		int id = q[i].id, l = q[i].l, r = q[i].r, res = 0;
		while (nl < l) del(nl++, res);
		while (nl > l) add(--nl, res);
		while (nr < r) add(++nr, res);
		while (nr > r) del(nr--, res);
		ans[id] = res;
	}
	for (int i = 0; i < m; i++) printf("%d\n", ans[i]);
	return 0;
}