洛谷 1494：[国家集训队] 小 Z 的袜子

/**
 * 莫队算法／Mo’s algorithm可用于离线无修改区间查询, 且已知[l, r]结果, 则可在
 * O(1)转移至[l, r + 1]者. 暴力需时 O(n^2),仅凭重排各查询, 效率即达 O(n√n).
 **/
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#define oxis 50003

struct query {
	// 各次查询按左端分块, 块大小 √n
	int l, r, block, order;
};	

/**
 * 排序查询, 第一关键字为左端所在块, 第二关键字为右端. 如此, 共分√n块, 每块之内
 * 左右转移至多 n次, 故单块需时 O(n),共需 O(n√n).
 **/
int cmp(const void *u, const void *v)
{
	const struct query
		*u2 = (const struct query *)u, *v2 = (const struct query *)v;
	if (u2->block != v2->block)
		return u2->block - v2->block;
	else
		return u2->r - v2->r;
}

int gcd(int u, int v)
{
	return v ? gcd(v, u % v) : u;
}

int main(void)
{
	int n, m, i, l = 1, r = 1, ans = 0;
	static int c[oxis], count[oxis], ans1[oxis], ans2[oxis];
	static struct query lr[oxis];

	scanf("%d%d", &n, &m);
	for (i = 1; i <= n; ++i)
		scanf("%d", i + c);
	for (i = 0; i < m; ++i) {
		scanf("%d%d", &lr[i].l, &lr[i].r);
		lr[i].order = i;
		lr[i].block = lr[i].l / block_size;
	}
	int block_size = sqrt(n);		// 块大小
	qsort(lr, m, sizeof(struct query), cmp);

	count[c[1]] = 1;
	for (i = 0; i < m; ++i) {
		const struct query *cur = lr + i;
		int order = cur->order;
		if (cur->l == cur->r) {
			// 数据错误所致例外
			ans1[order] = 0;
			ans2[order] = 1;
			continue;
		}
/**
 * 四个 while即完成转移. 某区间中, 若有 n个红色, 则有n(n - 1)个同色对, 与位置无
 * 关. 各颜色相加, 即得同色对总数, 从而得概率. 因此, 转移遇第 n个同色, 则贡献为
 * (n - 1).
 **/
		while (l < cur->l)
			ans -= --count[c[l++]];
		while (l > cur->l)
			ans += count[c[--l]]++;
		while (r < cur->r)
			ans += count[c[++r]]++;
		while (r > cur->r)
			ans -= --count[c[r--]];
		// 以下处理除法
		long long int span = cur->r - cur->l;
		int top = ans;
		int bottom = span * (span + 1) / 2;
		int common = gcd(top, bottom);
		ans1[order] = top / common;
		ans2[order] = bottom / common;
	}
	for (i = 0; i < m; ++i)
		printf("%d/%d\n", ans1[i], ans2[i]);
	return 0;
}