基础莫队

更洛谷的观感体验。

今天讲一下基础的莫队算法。

算法思路

暴力

每次统计每个数有几次，再累加，时间复杂度为 $O(nm)$。
0分（全 TLE） 不是这题卡这么紧。

#include<bits/stdc++.h>
using namespace std;
int n,m,k,a[50010]; 
int main()
{
	cin >> n >> m >> k;
	for(int i = 1;i <= n;i++)
		scanf("%d",&a[i]);
	while(m--)
	{
		int l,r,ans = 0;
		scanf("%d%d",&l,&r);
		map<int,int> c;//直接开数组也可以
		for(int i = l;i <= r;i++)
			c[a[i]]++;//累加
		for(int i = 1;i <= k;i++)
			ans += c[i] * c[i];//加上平方
		cout << ans << endl;
	}
	return 0;
}

优化

思路

上面的暴力代码是在线的，而换成离线呢？
在线定义：输入后会立刻输出结果。
离线定义：输入完才会按顺序输出结果。

那我们就可以优化，下一个答案根据上一个答案转移出来。
定义一个 add 和 del 函数，用来添加和删除数据。

代码

那每次会对答案加上多少呢？
$c_i$ 加上 $1$ 的平方和 $c_i^2$ 的差，$(c_i + 1) ^ 2 - c_i ^ 2$。
$(c_i + 1) ^ 2 - c_i ^ 2 \\ = (c_i + 1 + c_i)(c_i + 1 - c_i)\\ =2c_i + 1$

减去也一样。
$c_i ^ 2 - (c_i - 1) ^ 2\\ =(c_i + c_i - 1)(c_i - c_i + 1)\\ =2c_i - 1$

上代码

#include<bits/stdc++.h>
using namespace std;
int n, m, k, a[50010], c[50010];
long long ans;
struct point
{
	int l, r;
}q[50010];
void add(int x)
{
	ans += 2 * c[x] + 1;
	c[x]++;
}
void del(int x)
{
	ans -= 2 * c[x] - 1;
	c[x]--;
}
int main()
{
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++)
		scanf ("%d", &a[i]);
	for (int i = 1; i <= m; i++)
		scanf ("%d%d", &q[i].l, &q[i].r);
	int l = 1, r = 0;
	for (int i = 1; i <= m; i++)
	{
		int ql = q[i].l, qr = q[i].r;
		/*注意，应该先写扩大再缩小，不然可能会负数*/
		/*先扩大再添加*/
		while (l > ql) l--, add(a[l]);
		while (r < qr) r++, add(a[r]);
		/*先删除再缩小*/
		while (l < ql) del(a[l]), l++;
		while (r > qr) del(a[r]), r--;
		cout << ans << endl;
	}
	return 0;
}

全 TLE

时间复杂度

add 和 del 的时间复杂度为 $O(1)$，
每次扩大或缩小时间复杂度最坏为 $O(n)$，
一共执行了 $m$ 次扩大缩小。
时间复杂度为 $O(nm)$ 没优化？。

再优化

思路和代码

我们发现如果排序了数组就可以优化时间复杂度，可如何排序呢？

我们把一个 $a$ 这个数组分成几个区间，每个区间长度为 $B$。
$B = 2$ 时，图是这样的：
$\Box\Box|\Box\Box|\Box\Box|\Box\Box|\Box$。
我们统一排序右端点，得到以下表达式：
cmp:$\begin{cases}x.l < y.l & \text{if} & \frac{x.l}{B} = \frac{y.l}{B}\\ x.r < y.r & \end{cases}$
写出代码：

bool cmp(point x, point y)
{
	if (x.l / B != y.l / B) return x.l < y.l;
	return x.r < y.r;
}

那 $B$ 选几合适呢？
设 $\sqrt{n}$，这样就可以分成 $n$ 个区间。

上代码：

#include<bits/stdc++.h>
using namespace std;
int n, m, k, a[50010], c[50010], B;
long long now, ans[50010];//now为当前的答案，ans[i]为第i个询问的答案
struct point
{
	int l, r, id;
}q[50010];
bool cmp(point x, point y)
{
	if (x.l / B != y.l / B) return x.l < y.l;
	return x.r < y.r;
}
void add(int x)
{
	now += 2 * c[x] + 1;
	c[x]++;
}
void del(int x)
{
	now -= 2 * c[x] - 1;
	c[x]--;
}
int main()
{
	cin >> n >> m >> k, B = sqrt(n);
	for (int i = 1; i <= n; i++)
		scanf ("%d", &a[i]);
	for (int i = 1; i <= m; i++)
		scanf ("%d%d", &q[i].l, &q[i].r), q[i].id = i;//记录每个点原来的id
	sort(q + 1, q + m + 1, cmp);
	int l = 1, r = 0;
	for (int i = 1; i <= m; i++)
	{
		int ql = q[i].l, qr = q[i].r id = q[i].id;
		while (l > ql) l--, add(a[l]);
		while (r < qr) r++, add(a[r]);
		while (l < ql) del(a[l]), l++;
		while (r > qr) del(a[r]), r--;
		ans[id] = now;
	}
	for(int i = 1; i <= m; i++)
		cout << ans[i] << endl; 
	return 0;
}

AC记录。

时间复杂度分析

设第 $i$ 个区间的最大 $l$ 为 $max_i$。
排序后：$max_1 \le max_2 … \le max_{\sqrt{n}}$。
每一次操作最坏的时间复杂度为 $O(n)$。
所有块的总和就是$O(n\sqrt{n})$。
重点分析 $l$：因为每一次改变的时间复杂度都是 $O(max_i-max_{i-1})$ 的，所以在同一块中时间复杂度为 $O(\sqrt{n}(max_i-max_{i-1}))$。
求和
$\begin{aligned} & O(\sqrt{n}(\max{}_1-1)+\sqrt{n}(\max{}_2-\max{}_1)+\sqrt{n}(\max{}_3-\max{}_2)+\cdots+\sqrt{n}(\max{}_{\lceil\sqrt{n}\rceil}-\max{}_{\lceil\sqrt{n}\rceil-1))} \\ = \phantom{} & O(\sqrt{n}\cdot(\max{}_1-1+\max{}_2-\max{}_1+\max{}_3-\max{}_2+\cdots+\max{}_{\lceil\sqrt{n}\rceil-1}-\max{}_{\lceil\sqrt{n}\rceil-2}+\max{}_{\lceil\sqrt{n}\rceil}-\max{}_{\lceil\sqrt{n}\rceil-1)}) \\ = \phantom{} & O(\sqrt{n}\cdot(\max{}_{\lceil\sqrt{n}\rceil-1}))\\ \end{aligned}$