普通莫隊算法筆記

應用：

莫隊算法是求離線區間詢問問題的算法，離線的意思就是上一次的結果并不會作為下一次的詢問要求的且隻查找詢問不會修改的。時間複雜度為O(n*sqrt(n))，可以說是極大的降低了時間複雜度。

原理

對于一個離線區間詢問問題，如果知道了區間[l, r]的結果就可以在O(1)内直到[l-1, r]或者 [l+1, r] 或者 [l, r-1] 或者 [l, r+1] 的結果。是以這個算法把整個資料n分成了n/ ( n ) \sqrt(n) (

​n) 塊，然後通過對詢問排序預處理，預處理過程就是如果兩個區間左指針在一個分塊内，就按照右指針進行排序，否則就按照左指針進行排序，這個可以通過sort簡單做。然後再不斷地進行左右指針移動來計算就可以了。至于原理我也不太懂，不過可以去看看莫濤的論文去。

一半莫隊的題都需要快讀的闆子，因為資料量都有比較大。

例題

[2009國家集訓隊]小Z的襪子(hose)

思路非常簡單，多一個後先減去原來的，再加上多一個後的組合數就行了。

ac代碼

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

using namespace std;

typedef long long ll;
ll a[50005], cnt[50005];

inline ll read() {
	ll res = 0;
	char c = getchar();
	while (!isdigit(c)) c = getchar();
	while (isdigit(c)) res = (res << 1) + (res << 3) + c - 48, c = getchar();
	return res;
}

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

struct quary
{
	ll l, r, id, b;
}q[50005];

struct ans
{
	ll s, x;
}ans[50005];

inline bool cmp(struct quary x, struct quary y)
{
	if (x.b == y.b)
		return x.r < y.r;

	return x.l < y.l;
}

int main()
{
	ll n, m;

	n = read(), m = read();

	ll s = sqrt(n);

	for (int i = 1; i <= n; i++)
	{
		a[i] = read();
	}

	for (int i = 0; i<m; i++)
	{
		q[i].l = read(), q[i].r = read();
		q[i].id = i;
		q[i].b = q[i].l / s;
	}

	sort(q, q + m, cmp);

	ll l = 1, r = 0, Ans = 0;

	for (int i = 0; i<m; i++)
	{
		while (l > q[i].l)
		{
			++cnt[a[--l]], Ans -= (cnt[a[l]] - 2) * (cnt[a[l]] - 1) / 2;
			Ans += (cnt[a[l]] - 1) * cnt[a[l]] / 2;
		}

		while (r < q[i].r)
		{
			++cnt[a[++r]], Ans -= (cnt[a[r]] - 2) * (cnt[a[r]] - 1) / 2;
			Ans += (cnt[a[r]] - 1) * cnt[a[r]] / 2;
		}

		while (l < q[i].l)
		{
			--cnt[a[l]], Ans -= (cnt[a[l]] + 1) * cnt[a[l]] / 2;
			Ans += (cnt[a[l]]) * (cnt[a[l]] - 1) / 2;
			l++;
		}

		while (r > q[i].r)
		{
			--cnt[a[r]], Ans -= (cnt[a[r]] + 1) * cnt[a[r]] / 2;
			Ans += cnt[a[r]] * (cnt[a[r]] - 1) / 2;
			r--;
		}

		ll temp = (q[i].r - q[i].l + 1) * (q[i].r - q[i].l) / 2;
		ll num = gcd(temp, Ans);
		ans[q[i].id].s = Ans / num;
		ans[q[i].id].x = temp / num;
	}

	for (int i = 0; i<m; i++)
	{
		if (ans[i].s)
			printf("%lld/%lld\n", ans[i].s, ans[i].x);
		else
			puts("0/1");
	}

	return 0;
}