AC 记录

#include <cmath>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 5e4 + 5;

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

ll res;
int len;
ll ans[N];
int a[N], cnt[N];

inline int get(int x)
{
	return x / len;
}

inline bool cmp(const node &x, const node &y)
{
	int xl = get(x.l), yl = get(y.l);
	if(xl == yl) return xl < yl;
	if(xl % 2 == 1) return x.r < y.r;
	return x.r > y.r;
}

inline void add(int x)
{
	res -= (ll)cnt[x] * cnt[x];
	cnt[x] ++ ;
	res += (ll)cnt[x] * cnt[x];
}

inline void del(int x)
{
	res -= (ll)cnt[x] * cnt[x];
	cnt[x] -- ;
	res += (ll)cnt[x] * cnt[x];
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m, k;
	cin >> n >> m >> k;
	for(int i = 1; i <= n; ++ i)
		cin >> a[i];
	for(int i = 1; i <= m; ++ i)
	{
		int l, r;
		cin >> l >> r;
		q[i] = {i, l, r};
	}
	len = sqrt((double)n * n / m);
	if(!len) len = sqrt(n);
	sort(q + 1, q + m + 1, cmp);
	for(int k = 1, i = 0, j = 1; k <= m; ++ k)
	{
		int l = q[k].l, r = q[k].r;
		while(i < r) add(a[ ++ i]);
		while(i > r) del(a[i -- ]);
		while(j < l) del(a[j ++ ]);
		while(j > l) add(a[ -- j]);
		ans[q[k].id] = res;
	}
	for(int i = 1; i <= m; ++ i) cout << ans[i] << '\n';
}

注意到 cmp 函数内：

if(xl == yl) return xl < yl;

应该会 TLE，结果被我卡过去了，建议加强数据！