普通莫队算法笔记

应用：

莫队算法是求离线区间询问问题的算法，离线的意思就是上一次的结果并不会作为下一次的询问要求的且只查找询问不会修改的。时间复杂度为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;
}