标签：cnt 分块询问 sqrt 端点莫队复杂度

【根号分治】

例题：等差数列加

给定一个长度 \(n\) 的数列，初始全都是 0。（\(n\leq 2\times 10^5\)）

要求支持两种操作：

\(1\;x\;y\;d\)，表示把所有下标模 \(x\) 等于 \(y\) 的位置全部加上 \(d\)；
\(2\;x\)，表示查询 \(a_x\) 当前值。

做法：

对于所有 \(x>\sqrt n\)，我们直接暴力循环修改；

否则，在 \(tag\) 数组上打标记：\(tag[a][b]\) 表示模 \(a\) 得 \(b\) 的位置总共加上了 \(tag[a][b]\)。

在我们查询的时候，先 \(ans=a[x]\)，然后循环 \(i\leftarrow 1\sim \sqrt n\)，令 \(ans\;+\!\!=\;tag[i][x\!\! \mod i]\)。然后输出 \(ans\) 即可。

这个复杂度是 \(O(n\sqrt n)\)。

cin >> n >> q;
int M = 500; //因为根号2e5差不多500
for (int i = 1; i <= q; i++) {
	int opt, x;
    cin >> opt >> x;
    if (opt == 1) {
    	int y, d;
        cin >> y >> d;
        if (x <= M)
        	tag[x][y] += d; //小于等于M,打标记
        else
        	for (int j = y; j <= n; j += x) //暴力修改
            	a[j] += d;
    }
    else {
    	long long ans = a[x];
        for (int j = 1; j <= M; j++)
        	ans += tag[j][x % j];
        cout << ans << endl;
    }
}

图染色：

给定一张 \(n\) 点 \(m\) 边的图，每个点初始白色。要求支持两个操作：

1 x，表示翻转点 \(x\) 的颜色；
2 x，表示查询 \(x\) 有多少个黑色的邻居。

一般图上的根号分治，按照点的度数分类。

做法：

所有点的度数之和为 \(2m\)。

设一个阈值 \(T\)。度数 \(\geq T\) 的称为大点，\(<T\) 的是小点。

对于翻转操作：

修改一个点时，我们同时更新其周围大点的答案。

因为大点个数 \(O(\frac{m}{T})\)，所以翻转操作 \(O(\frac{m}{T})\)。

（当然，一个点周围的大点有谁肯定要预处理）

对于查询操作：

如果该点为大点，我们在翻转操作的时候已经记录了答案。\(O(1)\) 复杂度。

如果该点为小点，直接暴力计算邻居。\(O(T)\) 复杂度。

两个复杂度取平均，\(O(\sqrt m)\) 的总时间复杂度。

【莫队】

莫队的思想可以概括为：

询问排序，区间移动，离线处理

【基础莫队】

以两道例题说明莫队的思想。

小Z的袜子

给出一个 \(n\) 长度序列。每次询问给出 \(l,r\)，回答在 \([l,r]\) 中任选两个数，这两个数相等的概率是多少。

前置思路：

我们想要维护一个区间内，每一个数的出现次数。因为这样我们可以用符合条件数 / 总可能数得到概率。

这个用线段树不好做，因为两个区间合并难以 \(O(1)\) 计算。

但是，我们发现，假设我们已经算出了 \([l,r]\) 的 \(cnt\) 数组，那么 \([l+1,r]\) 的 \(cnt\) 数组就相当简单了： cnt[a[l]]-- 即可。并且此时 “符合条件数” 的变化同样简单：ans -= cnt[a[l]]。

同样地，\([l,r+1]\) 的求解也很简单。

题解：

把序列进行分块，\(\sqrt n\) 的长度做一块。

分别处理每一块，处理所有左端点在此块的询问。

对于每个询问，我们循环 \(R:1\sim n\)，并且在枚举 \(R\) 的同时维护 \(1\sim R\) 的 \(cnt\) 数组。

如果每个时刻 \(R\) 和一个询问 \([l,r]\)（当然注意这个询问的 \(l\) 一定在当前处理块中）的 \(r\) 相等了，我们把 \(L\) 移动到对应的 \(l\) 处，并且在移动的同时增加或减去 \(a[L]\)。

然后此时此刻，我们就可以回答这个 \([l,r]\) 的问题了。

回答完这个问题后，\(R\) 继续向右，\(L\) 不用动，直到下次 \(R\) 又碰到一个询问。

这个操作中，处理一个询问需要 \(O(\sqrt n)\) 的左端点移动，\(O(n)\) 的右端点移动。而一共有 \(O(\sqrt n)\) 个块，所以复杂度 \(O(n\sqrt n)\)。

小B的询问

分块和莫队在此题中的区别：

分块：分出 \(\sqrt n\) 个块，求出每个块里每个数的出现次数，询问时新建一个 \(cnt\) 数组，把经过的所有块的次数都加起来。

虽然分块本身只需要 \(O(m\sqrt n)\) 的时间复杂度，但是 “新建一个 \(cnt\) 数组” 需要 \(O(n)\)，总的还是 \(O(nm)\)。

莫队：同样分块，把每个询问先按左端点所在块的编号排序，然后再按右端点排序。

对于左端点在同一个块的询问，一次处理全部：枚举右端点 \(R:1\sim n\)，同时新建一个 \(cnt\) 数组，在枚举右端点的同时计算 \(1\sim R\) 的 \(cnt\) 数组。

如果当前枚举到的右端点刚好是某个询问的右端点，就开始调整左端点到这个询问的左端点。

为什么莫队算法也要新建一个 \(cnt\) 数组，但是却比分块更快呢？

因为分块是每一个询问都新建一次，而莫队是每一个块新建一次。

下面考虑一下莫队具体的时间复杂度。

外层有一个 \(O(\sqrt n)\) 的循环枚举块数。

内层有一个 \(O(n)\) 的循环枚举右端点。

对于每一个询问，最多使用 \(O(\sqrt n)\) 的量级时间计算它。（一个块内最多移动 \(O(\sqrt n)\)）次。

一共 \(m\) 个询问。

所以是 \(O(n\sqrt n + m\sqrt n)\)，但是 \(n,m\) 同级，所以 \(O(n\sqrt n)\)。

【莫队的代码结构】

莫队的关键词：询问排序，区间移动，离线处理。

我们在代码中对应的：排序的cmp函数，处理区间的del和add函数，把询问存下来的数组。

小Z的袜子有点注释的代码

【莫队的几何意义】

《算法竞赛》（罗勇军、郭卫斌著）上册 P220。

如果把每一个询问 \([l,r]\) 看作一个点 \((l,r)\)，那么时间复杂度就是从原点开始，找一个顺序走过所有点，相邻点的曼哈顿距离之和。

如果只是按 \(x\) 排序，\(y\) 轴上可能会有大幅度跳跃。

莫队把 \(y\) 的大幅度跳跃转换成了 \(x\) 上的限定在 \(\sqrt n\) 幅度内的跳跃。

【带修莫队】

数颜色

对于每一个查询，额外记录一个时间戳 \(t\)，表示在这个询问之前，执行了 \(t\) 个修改操作。

先按左端点所在块排序，再按右端点所在块排序，最后按 \(t\) 排序——这样相当于每个询问看作立体空间内的一个点 \((l,r,t)\)。

把每个修改操作提出来变成一个修改操作序列，每次处理询问的 \(t\) 就像处理基础莫队的 \(r\)，来回加修改/回退修改即可。

【回滚莫队】

回滚莫队一般用来处理区间扩张很好维护，但是区间收缩不好维护的情况。

例如求最大值。扩张时只需要取 max 即可；但是收缩时，我们需要堆来辅助求出新最大值。

历史研究

这题就是典型的扩张好求，收缩不好求。

回滚莫队的运行方式

前面的操作方式和基础莫队一样：按照左端点所在块和右端点把所有询问离线排序。

对于所有询问分两类：

左右端点在一个块内。直接暴力 \(O(\sqrt n)\)。
左右端点不在一个块内。（因为按照右端点排序，肯定先处理完了 1 类才处理 2 类）

右端点和基础莫队一样，单调向右移动。

每次处理一个询问，都把左端点的位置重新设为 “询问左端点所在块的下一个块的第一个位置”。

然后开变量记录：

\([\)“询问左端点所在块的下一个块的第一个位置”，“询问右端点”\(]\) 的所有收缩时不好维护的信息。

接下来，把左端点一直向左扩张到询问的左端点，此时可以算出询问的答案。

算完之后，把左端点再一个一个倒退回 “询问左端点所在块的下一个块的第一个位置”，在倒退过程中，顺便维护所有收缩时好维护的信息。等退到位置了，利用之前记录的变量重置所有收缩时不好维护的信息。

因为右端点不变，左端点还是在一个块内来回移动，所以复杂度不变。

（这比用堆来维护更快！）

【练习】

Friendly pairs

查询区间内有多少对数差不超过 \(k\)。

离散化（巧）：先把所有数、所有数 - k、所有数 + k 都离散化了，这样就能快速判断。

然后用一个 BIT 维护当前区间内每个数的个数，开一个变量记录个数。然后就是莫队。

标签：cnt,分块,询问,sqrt,端点,莫队,复杂度
From： https://www.cnblogs.com/FLY-lai/p/18020663

莫队与分块