小Z的袜子

【题目链接】小Z的袜子

【题目类型】莫队算法

&题解：

莫队算法第一题吧,建议先看这个理解算法,之后在参考这个就可以写出简洁的代码

我的比第2个少了一次sort,他的跑了1600ms,我的跑了800ms.

【时间复杂度】\(O(n^{1.5})\)

&代码：

#include <cstdio>

#include <bitset>

#include <iostream>

#include <set>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <map>

#include <queue>

#include <vector>

using namespace std;

#define INF 0x3f3f3f3f

#define ll long long

const int maxn = 5e4 + 7;

int n, m, col[maxn], pos[maxn], ans, num[maxn];

ll fz[maxn], fm[maxn];

struct data { int l, r, id; } a[maxn];

bool cmp(data a, data b) {

	if(pos[a.l] == pos[b.l]) return a.r < b.r;

	return a.l < b.l;

}

void update(int x, int d) {

	int c = col[x];

	ans -= num[c] * num[c];

	num[c] += d;

	ans += num[c] * num[c];

}

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

int main() {

	//("E:1.in", "r", stdin);

	while(~scanf("%d%d", &n, &m)) {

		int bk = sqrt(n);

		for(int i = 1; i <= n; i++) {

			scanf("%d", col + i);

			pos[i] = (i - 1) / bk;

		}

		for(int i = 1; i <= m; i++) {

			scanf("%d%d", &a[i].l, &a[i].r);

			a[i].id = i;

		}

		sort(a + 1, a + 1 + m, cmp);

		memset(num, 0, sizeof(num));

		ans = 0;

		for(int i = 1, l = 1, r = 0; i <= m; i++) {

			for(; r < a[i].r; r++)

				update(r + 1, 1);

			for(; r > a[i].r; r--)

				update(r, -1);

			for(; l < a[i].l; l++)

				update(l, -1);

			for(; l > a[i].l; l--)

				update(l - 1, 1);

			if(a[i].l == a[i].r) {

				fz[a[i].id] = 0, fm[a[i].id] = 1;

				continue;

			}

			//引用& 是跟着变量的,不是跟着类型的

			ll &tz = fz[a[i].id], &tm = fm[a[i].id];

			tz = ans - (a[i].r - a[i].l + 1);

			tm = (ll)(a[i].r - a[i].l + 1) * (a[i].r - a[i].l);

			ll k = gcd(tz, tm);

			tz /= k, tm /= k;

		}

		for(int i = 1; i <= m; i++) {

			printf("%lld/%lld\n", fz[i], fm[i]);

		}

	}

	return 0;

}