小Z的袜子 & 莫队

莫队学习 & 小Z的袜子

引入

莫队由莫涛巨佬提出,是一种离线算法运用广泛

可以解决广大的离线区间询问题

莫队的历史

早在mt巨佬提出莫队之前类似莫队的算法和莫队的思想已在Codeforces

的高手圈中小范围的流传但mt是首位对莫队进行具体归纳总结的人

经过OIer和ACMer的改造延伸出了许多扩展莫队如回滚莫队

可是俺只会普通莫队这个坑还是以后再填吧（逃）

经典

学习

蒟蒻的我:莫队长啥样

见到mt本人就知道了

区间$[l,r]$可以在$O(1)$的时间里求出相邻区间的贡献

即$[l,r + 1]$,$[l + 1,r]$,$[l - 1,r]$,$[l,r - 1]$

那么你就可以在$O(n \sqrt n)$的时间里解决问题

思路

我们维护两个指针$l和r$在数组上跳来跳去

但若只是如此那么莫队是无法焕发容光的

你会发现若按读入的顺序跳来跳去那么就会非常的Crazy

而且复杂度最高就爆掉了达到了惊人de$O(n^2)$

对于莫队的题出题人不可能让你过的（除非数据过水

那么我们需要一个精美绝伦的$std::sort$让它跳得近一些

这样就可以有效地减少重复跳跃的路径

于是就变成了离线(没听说过有在线的莫队

莫队就大概是这样了吧

例题 & 实现

小Z的袜子

莫队的板子竟然是当年的国家集训队

可见莫队的用处还是挺大的况且NOI大纲上莫队好像是提高组的（没看过awa

对于区间$[l,r]$内

每种颜色的袜子的贡献为$sum[col[x]] * (sum[col[x]] - 1)$

其中sum[i]表示颜色为i的袜子的数量（当前区间$[l,r]$）

那么我们就有了如下更新

void revise(int x, int v) {ans -= sqr(sum[col[x]]), sum[col[x]] += v, ans += sqr(sum[col[x]]);}

对于之前的莫队形式我们用$[l,r]$做如下的更新

while(l < Katze[i].l) revise(l, -1), ++l;

while(l > Katze[i].l) revise(l - 1, 1), --l;

while(r < Katze[i].r) revise(r + 1, 1), ++r;

while(r > Katze[i].r) revise(r, -1), --r;

这时候我们算一下复杂度并且构造一下那个美妙绝伦的$std::sort$

我们将询问分块设块的大小为$size$

分类讨论一下

l和下一次询问的l不在同一块内需要至多$2 \times size$次移动共有$m$次询问时间复杂度为$O(m \times size)$
l和下一次询问的l在同一块内最好的情况（可控）就是$O(\frac{n ^ 2}{size}) $具体如下

当l所在块相同时才会有序此时我们在l所在块相同的时候按排序那么我们就可以把sort写成这样

struct Feder_der_Katze{

	int l, r, id;

	int ans1, ans2;

	friend bool operator < (const Feder_der_Katze a, const Feder_der_Katze b) {

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

		else return a.l < b.l;

	}

}Katze[N];

bool compare(Feder_der_Katze a, Feder_der_Katze b) {

	return a.id < b.id;

}

那么我们跑一个块r最多跳$O(n)$次总复杂度就是$O(\frac{n ^ 2}{size})$

综上所述复杂度应该是$O(n\sqrt n + \frac{n^2}{size})$

根据不等式的知识来讲大约在$size = sqrt(n)$也是一般情况下最优

总的时间复杂度$大常数C * O(n\sqrt n) = O(跑得过)$

温馨提示

本题中注意事项:

询问的$l = r$需要特判
写sort的时候是$l所属的块相等时判r 不一定是l相等$

别问怎么知道的不会Wrong Answer 但会Time Limit Exceeded$

Code

#include <bits/stdc++.h>

using namespace std;

int read(int x = 0, bool f = false, char ch = getchar()) {

	for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');

	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);

	return f ? ~x + 1 : x;

}

const int N = 5e4 + 5;

int n, m, siz, ans;

int col[N], bel[N], sum[N];

struct Feder_der_Katze{

	int l, r, id;

	int ans1, ans2;

	friend bool operator < (const Feder_der_Katze a, const Feder_der_Katze b) {

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

		else return a.l < b.l;

	}

}Katze[N];

bool compare(Feder_der_Katze a, Feder_der_Katze b) {

	return a.id < b.id;

}

int gcd(int x, int y) {return !y ? x : gcd(y, x % y);}

int sqr(int x) {return x * x;}

void revise(int x, int v) {ans -= sqr(sum[col[x]]), sum[col[x]] += v, ans += sqr(sum[col[x]]);}

signed main() {

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

	for (int i = 1; i <= n; ++i) col[i] = read(), bel[i] = i / siz + 1;

	for (int i = 1; i <= m; ++i) Katze[i].l = read(), Katze[i].r = read(), Katze[i].id = i;

	sort(Katze + 1, Katze + 1 + m); int l = 1, r = 0;

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

		while(l < Katze[i].l) revise(l, -1), ++l;

		while(l > Katze[i].l) revise(l - 1, 1), --l;

		while(r < Katze[i].r) revise(r + 1, 1), ++r;

		while(r > Katze[i].r) revise(r, -1), --r;

		if (Katze[i].l == Katze[i].r) {Katze[i].ans1 = 0, Katze[i].ans2 = 1; continue;}

		Katze[i].ans1 = ans - (Katze[i].r - Katze[i].l + 1);

		Katze[i].ans2 = (Katze[i].r - Katze[i].l + 1) * (Katze[i].r - Katze[i].l);

		int Gcd = gcd(Katze[i].ans1, Katze[i].ans2);

		Katze[i].ans1 /= Gcd, Katze[i].ans2 /= Gcd;

	} sort(Katze + 1, Katze + 1 + m, compare);

	for (int i = 1; i <= m; ++i) printf("%d/%d\n", Katze[i].ans1, Katze[i].ans2);

	return 0;

}

巴特西