70pts TLE on #7#8#9求调

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

int n, m;
const int N = 2e6+10;
int cnt[N], a[N], s[N], ans[N], st[N];
int l = 1, r = 0, now = 0;
int l1[N], r1[N];

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

inline bool cmp(node a, node b) {return (s[a.r] ^ s[b.r]) ? a.l < b.l : a.r < b.r;}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	// 分块
	for (register int i = 1; i <= ceil((double)n / sqrt(n*2/3)); i++)
		for (int j = (i-1) * sqrt(n*2/3) + 1; j <= i * sqrt(n*2/3); j++)
			s[j] = i;
	// 处理问询 
	for (register int i = 1; i <= m; i++)
	{
		cin >> q[i].l >> q[i].r;
		q[i].id = i;
		l1[i] = q[i].l;
		r1[i] = q[i].r;
	}
	// 排序
	sort(q+1, q+m+1, cmp); 
	for (int i = 1; i <= m; i++)
	{ 
		// 跑莫队
//		// l左移 
//		while (l < q[i].l) now -= !--cnt[a[l++]];
//		// l右移
//		while (l > q[i].l) now += !cnt[a[--l]]++;
//		// r右移
//		while (r < q[i].r) now += !cnt[a[++r]]++;
//		// r左移
//		while (r > q[i].r) now -= !--cnt[a[r--]];
		while(l < q[i].l) now -= st[a[l]] * (st[a[l]]-1)/2, st[a[l]]--, now += st[a[l]] * (st[a[l]]-1)/2, l++;
		while(l > q[i].l) now -= st[a[--l]] * (st[a[l]]-1)/2, st[a[l]]++, now += st[a[l]] * (st[a[l]]-1)/2;
		while(r < q[i].r) now -= st[a[++r]] * (st[a[r]]-1)/2, st[a[r]]++, now += st[a[r]] * (st[a[r]]-1)/2;
		while(r > q[i].r) now -= st[a[r]] * (st[a[r]]-1)/2, st[a[r]]--, now += st[a[r]] * (st[a[r]]-1)/2, r--;
		ans[q[i].id] = now;
	}
	for(register int i = 1, x; i <= m; i++)
	{
		x = __gcd ((long long)ans[i], (long long)(r1[i]-l1[i]+1) * (r1[i]-l1[i])/2);
		if(l1[i] == r1[i]) cout << "0/1" << '\n';
		else cout << ans[i]/x << "/" << (long long)((r1[i]-l1[i]+1) * (r1[i]-l1[i])/2)/x << '\n';
	}
	return 0;
}