我这一周都在写暴力。

根号分治

其实就是把两个暴力拼起来，只不过我们可以规定一个范围 $B$ ，使得这两种暴力都可以利用这个限制满足题目限制的时间。

AT_abc259_h [ABC259Ex]Yet Another Path Counting

题目描述

给你一个网格图，每个方格都有一个标签，每次从某个节点出发，每一步只能往右或往下，最终必须停在和起点标签相同的位置，问不同路径数量。

$1 \leq N \leq 400$ 。

思路

对于固定的标签我们可以对着整个网格图跑一个 dp 来算答案，也可以枚举起始点和结束点用组合数算答案，前者需要颜色的个数尽量小，后者需要网格次数尽量小。

所以我们可以按照出现次数分开处理颜色，如果按照出现次数与 $B$ 的关系分开，总的时间复杂度就是 $O(nB^2 + \displaystyle\frac{n^4}{B})$ ，令 $B = n$ 就可以得到 $O(n^3)$ 的复杂度，这题就过了。

对于组合数和 dp 的过程都很简单，我就不写了。

P1989 【模板】无向图三元环计数

题目描述

给定一个 $n$ 个点 $m$ 条边的简单无向图，求其三元环个数。

$1 \le n \le 10^5$ ， $1 \le m \le 2 \times {10}^5$ 。

思路

对于边 $(u,v)$ ，如果 $u$ 的总度数小于 $v$ 的或者两个点度数一样但 $u < v$ ，就在新的图里连 $(u,v)$ ，反过来连 $(v, u)$ 。

这样在新图里暴力答案肯定是对，但是时间复杂度其实是 $O(m \sqrt{m})$ 的。

因为对于度数小于 $\sqrt{m}$ 的边的贡献就是 $O(m \sqrt{m})$ ，大于 $\sqrt{m}$ 的只会有 $\sqrt{m}$ 个点和它连边，所以也是 $O(m \sqrt{m})$ 。

P8250 交友问题

题目描述

给你一个无向图，每次询问你 $u$ 有多少个邻居和 $v$ 不相连。

$1 \leq n, q \leq 2 \times 10^5$ ， $1 \leq m \leq 7 \times 10^5$ 。

思路

按照邻居数量分类，那么大点最多 $\displaystyle\frac{n}{B}$ 个。

如果查询的是两个小点，那就直接用 unordered_map 查询。时间复杂度 $O(qB)$ 。

如果查询的是两个大点，提前用bitset 维护大点的邻居直接算出答案。空间复杂度是 $O(\displaystyle\frac{n^2}{B})$ 。

如果查询的是一大一小，小的邻居在大的 bitset 里面找就好，时间复杂度 $O(qB)$ 。

为了保证不 MLE 也不 TLE，我们可以取 $B = 40$ 。

分块

就是把要维护的数据分成一块块处理，如果信息没有办法快速打标记或者合并的时候可以用。

一般来说我们要维护一个整块内的东西让它好查询和修改，查询就是整块之间一块块做，散块直接暴力。

P13977 数列分块入门 2

题目描述

给一个长度为 $n$ 的数列，有 $n$ 次操作，每次是区间加或者求区间内小于某个数的个数。

$1 \leq n \leq 200000$ 。

思路

把每 $B$ 个元素看作一块，对于一块内我们把里面的元素始终排好序，维护一个块上的懒标记。那么会有 $\displaystyle\frac{n}{B}$ 个块，每次重建块（就是牌排序）的时间复杂度是 $O(B \log B)$ 。

对于修改操作就是散块直接暴力改，整块就修改懒标记，散块修改完记得重建块。时间复杂度 $O(\displaystyle\frac{n}{B} + B \log B)$ 。

对于查询操作就是散块暴力，在整块里二分，时间复杂度 $O(\displaystyle\frac{n}{B} \log B)$

于是我们取 $B = \sqrt{n}$ 就能过。

P5356 [Ynoi Easy Round 2017] 由乃打扑克

题目描述

由乃给你一个长为 $n$ 的序列 $a$ ，需要支持 $m$ 次操作，操作有两种：

查询区间 $[l,r]$ 的第 $k$ 小值。
区间 $[l,r]$ 加上 $k$ 。

$1\leq l\leq r \leq n\leq 10^5$ ， $1 \leq m \leq 10^5$ ， $-2\times 10^4\leq a_i, k\leq 2\times 10^4$ 。

思路

还是每 $B$ 个元素分一块，修改的逻辑就和我们前面一样。

对于查询，我们可以先找出当前区间的最大值和最小值，然后二分答案，具体来说就是在散块里面暴力计算，然后在排好序的整块里直接二分即可。

莫队

优雅的暴力。

普通莫队

概述

如果我们知道了 $[l,r]$ 的答案，并且左右端点只移动 $1$ 之后的区间的答案非常好由当前答案推出，就可以考虑用莫队。

我们先把所有查询的区间 $[q_l, q_r]$ 按照 $q_l$ 分块，也就是按照 $q_l / B$ 排序，然后一块内部按照 $r$ 排序，然后按照顺序处理查询。

处理的时候我们维护当前区间的左右端点 $[l,r]$ ，然后维护两个操作，分别是左右端点向左或者右扩展一个元素和收缩一个元素的时候对区间答案的更新。

while (l > q[i].l) {
    l--;
    add(l);
}
while (l < q[i].l) {
    del(l);
    l++;
}
while (r > q[i].r) {
    del(r);
    r--;
}
while (r < q[i].r) {
    r++;
    add(r);
}

这个时候区间就是查询的区间了。

然后你发现令 $B = \sqrt{n}$ ，会有 $\sqrt{n}$ 个块，每次 $r$ 从数组移动过去最多 $\sqrt{n}$ 次，所以总的时间复杂度就是 $O(n \sqrt{n})$ 。

P2709 【模板】莫队 / 小 B 的询问

题目描述

每次询问区间 $[l,r]$ ，求：

小 B 有一个长为 $n$ 的整数序列 $a$ ，值域为 $[1,k]$ 。
他一共有 $m$ 个询问，每个询问给定一个区间 $[l,r]$ ，求：

\sum\limits_{i=1}^k c_i^2

其中 $c_i$ 表示数字 $i$ 在 $[l,r]$ 中的出现次数。

$1\le n,m,k \le 10^5$ 。

思路

你只需要看懂上面我在说什么，实现就很简单了。每次更新区间我们就把当前的和减去旧的出现次数的平方，然后加上新的就可以了，代码非常好写。

P1997 faebdc 的烦恼

题目描述

求区间众数的出现次数。

对于全部的测试点，保证 $1 \leq n \leq 10^5$ ， $1 \leq q \leq 2\times 10^5$ ， $-10^5 \leq a_i \leq 10^5$ 。

思路

和上一道题的做法类似，但是发现如果只用一个数组记每个数的出现次数，删除操作就不是很好做了。

所以我们再用一个数组记出现次数的出现次数，那么如果删除的时候旧出现次数的出现次数等于 $0$ 还是当前答案，那么就需要把答案减一。其他的实现其实都类似。

回滚莫队

有的时候我们会遇到那种容易增加，但是从区间里面删东西的时候却不好做的题目。

我们可以把“删除”改为“撤销”，在避免删除的同时时间复杂度不变。

具体来说就是把左端点在同一块的查询放一起，右端点从小到大排序。我们在不停维护右端点的时候每次把左端点放在查询的块内最靠右的左端点位置，对于当前查询的区间就让左端点一步步往左扩展到我们想要查询的地方，然后再一步步退回起点。

P5906 【模板】回滚莫队&不删除莫队

题目描述

给定一个序列，多次询问一段区间 $[l,r]$ ，求区间中相同的数的最远间隔距离。

序列中两个元素的间隔距离指的是两个元素下标差的绝对值。

思路

这题的增加操作非常容易维护，明白了我上述的回滚莫队的过程就很好理解了。对于撤销，对于这道题完全可以直接记录数组，不过也可以记录更改的位置和旧的值。

细算一下时间复杂度发现其实回滚莫队和原本的莫队差不多。

AT_joisc2014_c 歴史の研究

题目描述

每次求给定区间里最大的重要度。一个元素的重要度定义为它的权值乘上在去区间里的出现次数。

$1\le Q,N\le 10^5$ ， $1\le X\le 10^9$ ， $1\le L\le R\le N$ 。

思路

发现这题也是增加好写删除不好写，只需要维护区间里数出现的次数然后每次增加只看看新加的能不能更新答案就好，其他的实现都很简单。

我好像根本没学明白。