浅 谈 分 块
w33z8kqrqk8zzzx33
2020-12-26 22:38:57
# 【块状链表的超高速实现】
众所周知 $vector$ 任何位置插入特别快，可以实现链表的插入删除操作，也可以实现任何位置的 $O(1)$ 查询修改操作。但是，实际上插入删除在 $vector$ 里仅仅是低常数 $O(n)$。如何继续优化？我们发现拼劲在于 $vector$ 的大小；如果 $vector$ 变过大，插入删除效率会降低。考虑利用根号平衡来对 $vector$ 大小设定上限。我们可以有序维护很多 $vector$ 来代表一个序列，同时保证所有 $vector$ 大小不超过一个上线。定这个上线为 $B$；如果所有元素数量为 $n$，会有 $n/B$ 个 $vector$。接下来实现几个基本操作：
- **建立块状链表。** 假设我们想从一个数组 $a$ 构造；可以依次提取数组的前 $B/2$ 元素当一个 $vector$ 添加。可能有用来添加一个哨兵元素在数组尾部。（应用 $B/2$ 的原因接下来讲。）
- **找到第 $k$ 元素。** 这里我们 $k$ 从 0 开始标号。我们依次遍历这些 $vector$。如果当前 $k$ 小于当前 $vector$ 大小，那么可以直接返回当前 $vector$ 的第 $k$ 元素。否则，这一个 $vector$ 的所有元素都在接下来的 $vector$ 的所有元素前面；从 $k$ 减除掉当前 $vector$ 大小。
- **插入。** 首先，我们需要知道插入的位置。为了方便默认是在给定插入位置的前面插入；直接用 $vector::insert$。**为了保证时间复杂度**，如果插入完导致这个 $vector$ 大于 $B$，则在 $B/2$ 处分裂这个 $vector$。具体怎么分裂：
1. 在块状链表里找到这个 $vector$ 接下来的 $vector$；在接下来的 $vector$ 之前插入一个新建的 $vector$。
2. 这个新建 $vector$ 应该保存刚才插入的 $vector$ 的 $B/2$ 元素后缀，也就是 $vector::end()-B/2,vector::end()$ 这个 $iterator$ 区间。可以用这个区间当参数做 $emplace\_back$。我们用 $B/2$ 分裂来平均分裂后的 $vector$ 长度，并同时保证没有 $vector$ 长度超过 $B$。这也是为什么我们在上面选取 $B/2$。
3. 建完新的 $vector$，再删除这个区间。
- **删除。** 同样找到位置，利用 $vector::erase$。如果这个 $vector$ 的大小变为零，把这个 $vector$ 从块状链表删除。
## 时间复杂度
以下默认 $q=O(n),B=O(\sqrt n)$。
定理：块状链表总共 $vector$ 数量不会超过 $O(\sqrt n)$。证明：只会有两个可能地方会对 $vector$ 数量产生贡献，建立和插入。建立会创建 $2n/B=O(n/B)$ 个 $vector$。插入复杂点。首先，删除肯定不会让块状链表或者任意一个 $vector$ 变长；对分析总 $vector$ 数量分析可以忽略删除操作。如果没有删除操作，所有 $vector$ 长度至少是 $B/2$；插入贡献的长度是 $O(n)$；于是插入贡献的 $vector$ 数量也是 $O(n/B)=O(\sqrt n)$。
引理：找第 $k$ 的时间复杂度是 $O(\sqrt n)$。证明：找第 $k$ 只需要遍历这个块状链表的外层；已经证明了外层大小是 $O(\sqrt n)$。
引理：插入的时间复杂度是 $O(\sqrt n)$。证明：首先，必定有 $O(\sqrt n)$ 从内层 $vector$ 插入来。当一个 $vector$ 需要分裂，则需要在外层插入一个新 $vector$；以上外层大小不超过 $O(\sqrt n)$。
引理：删除的时间复杂度是 $O(\sqrt n)$。证明：和插入时间复杂度同样。
于是整体任何操作的时间复杂度保证为 $O(\sqrt n)$，考虑到 $vector$ 插入删除的低常数，实际极其快。
## 例题1：数列分块入门 6
题意：在第 $k$ 插入；询问第 $k$ 值。
模板题。操作和以上描述的一样，还少了一个删除？~~话说为什么数据随机~~ 关于实现细节，可以外层叫“链表”的东西仍然用 $vector$ 实现，或者把块状链表看做一个 $vector$ 套 $vector$。写和跑都快。注意插入部分需要先应用第 $k$ 找到插入位置。
## 例题2：P4008 [NOI2003] 文本编辑器
题意：维护一个字符串，支持插入一串，删除一串，询问一串。
首先，move prev next 都是同一个操作穿不同的外装，维护一个正整数代表当前指针。
这里，如果按照以上方法暴力一个一个加入一个一个删除，操作复杂度 $O(|S|\sqrt n)$，理论上会炸上天。考虑如何降到 $O(\sqrt n+|S|)$。
- **维护：** 定义“维护”为保证：
- 当前的块状链表没有一个 $vector$ 长度超过 $O(B)$；
- 当前的块状链表没有一个空 $vector$。
- 和上一道题不同，现在可能有至多一个 $vector$ 长度无限，或者会有一个区间空 $vector$，会给定这个 $vector$ 的具体位置或首位置。具体做法：对于情况 1，把这串的结尾 $O(B)$ 字符分裂出来，插入到这个 $vector$ 后面，继续递归维护当前 $vector$。对于情况 2，删除这个 $vector$ 并且继续递归维护。
- **捆绑插入：** 可以直接找到对应 $vector$ 插入一大堆，然后调用“维护”。
- **捆绑删除：** 稍微复杂点，找到开始删除的地方，然后每次尽量删除可能多的值，知道遍历完或删完，然后调用“维护”。
- **捆绑输出：** 找到开始输出位置，和删除一样方法继续遍历。
接下来证明时间复杂度。
定理：对第一情况，“维护”和初始化一个关于维护的 $vector$ 的时间复杂度一样。这是由于“维护”和初始化其实进行的步骤完全一致。对第二情况，“维护”的时间复杂度上界为 $O(\sqrt n)$，因为最多可能有这么多 $vector$。
引理：插入时间复杂度是 $O(\sqrt n+|S|)$。插入会导致那一个 $vector$ 大小变大 $|S|$。
引理：删除时间复杂度是 $O(\sqrt n+\frac{|S|}{\sqrt n})$。找到位置需要 $O(\sqrt n)$；删除散块需要 $O(\sqrt n)$；删除整块总共需要 $O(\frac{|S|}{\sqrt n})$。可能由于需要回收空间而导致时间复杂度为 $O(\sqrt n+|S|)$。
引理：输出时间复杂度为 $O(\sqrt n+|S|)$。同样方法证明。
虽然长度能到 2e6，虽然卡满可以调用 3e6 次输出，STL 的常数是超级小。注意这里可以用 $basic\_string$ 继续简化代码。
## Final Boss: P6136 【模板】普通平衡树（数据加强版）
题意：维护一个 order statistic 集合。
首先，我们可以把“无序”变成“有序”：选择维护当前集合的排序顺序。
我们第一需要实现是找到一个元素会在哪里插入来保证有序性。如果一整个块状链表是有序，那么所有内层 $vector$ 结尾值也必定有序；找到第一个 $vector$ 结尾值大于等于给定值即可。我们永远可以在这个 $vector$ 里的某个地方插入这个给定值。根据块状链表大小定理，这的时间复杂度也是 $O(\sqrt n)$。
插入就直接这样（套普通块状链表插入方法）实现了，删除同理。第 $k$ 可以直接用朴素块状链表方法做。$rank$ 复杂一点：按照以上方法把给定值定位，并且统计在这个值前面的整块（依次遍历统计 $size$）和散块（还是暴力），时间复杂度是 $O(\sqrt n)$。
接下来就是 $pre$ $nxt$：
- $pre$ 等于一整个序列的 $lower\_bound$ 前面的值。定位之后对内层 $vector$ 做 $lower\_bound$（当然也可以暴力，但是这样更爽）如果 $lower\_bound$ 得到这个 $vector$ 的首元素，它前面的值是上一个 $vector$ 的末元素，特判。
- $nxt$ 等于一整个序列的 $upper\_bound$ 的值。定位之后对内层 $vector$ 做 $upper\_bound$。如果 $upper\_bound$ 得到 $end$，真真值是下一个 $vector$ 的首元素，特判。
块状链表可以称作“五分钟写完的平衡树”。
## 习题
- [P4278 带插入区间K小值](https://www.luogu.com.cn/problem/P4278)
# 【奇怪莫队】
众所周知莫队是分块，但是莫队不是数据结构
## P1972 [SDOI2009]HH的项链
~~你真觉得我会讲暴力莫队吗~~
注意直接 naive 莫队是过不了的。
考虑用 $pre$ 和 $nxt$ 数组莫队，其中 $pre[i]$ 等于 $a[i]$ 在数组里上一个出现位置，$nxt[i]$ 等于 $a[i]$ 在数组里下一个出现位置。
$i$ 会对 $[l,r]$ 产生贡献当且仅当：
- 如果 $i$ 在 $[l,r]$ 左侧，$r<nxt[i]$；
- 如果 $i$ 在 $[l,r]$ 右侧，$pre[i]<l$。
直接按照这些转移莫队，时间复杂度仍然是 $O(n\sqrt n)$。
## AT1219 歴史の研究
题意：区间 $max(i\times c_i)$，其中 $c_i$ 是区间出现次数。
这莫队能直接扩展，但是并不能按照普通办法随便删除。
继续抽象到二维平面上，我们现在只能往 $-x$ 或 $+y$ 方向走，因为普通删除是不可做。继续观察发现可以 **回滚**，因为每一次 $-x$ 或 $+y$ 仅仅修改 $O(1)$ 的状态位置，可以存在一个 $stack$ 里回滚。
我们现在想找到一个有向往外森林，使得方向全是 $-x$ 或 $+y$ 并且达到了所有询问节点和所有森林路径上的节点满足 $x\le y$，同时也需要保证复杂度。
首先特判所有询问长度 $<\sqrt n$ 的询问，因为这些询问比较难到达。特判完，存在询问的 $xy$ 位置会看的像这样：
```
.........
.........
.........
XXX......
XXX......
XXX......
XXXXXX...
XXXXXX...
XXXXXX...
```
这次我们按照 $y$ 轴分块：
```
.........
.........
.........
---------
XXX......
XXX......
XXX......
---------
XXXXXX...
XXXXXX...
XXXXXX...
```
于是可以在这些 `o` 点分别跑 $\sqrt n$ 次”莫队“ 处理这个块：
```
.........
.........
.........
---------
XXo......
XXX......
XXX......
---------
XXXXXo...
XXXXXX...
XXXXXX...
```
显然，从 `o` 开始的地方只需要 $-x$ 或者 $+y$：
```
.........
.........
.........
---------
++o......
VV.......
V........
---------
+<+-+o...
V.V.V....
..V......
```
然后就好了。
每一块需要左右遍历左右 $O(n)$，上下每一个询问需要上下遍历 $O(\sqrt n)$，总共 $O((n+q)\sqrt n)$。
貌似常数炸 >_>
## SP10707 COT2 - Count on a tree II
考虑树的欧拉序，两个节点之间永远存在恰好一个欧拉序里的区间代表路径。每一个节点都存两次 - 第一次代表 ”进入节点“，第二次代表 ”退出节点“。从 $u$ 到 $v$ 会一直退出到 LCA，然后一直进入到 $v$。任何在中间的节点也会被一个 dfs 遍历到 - 但是会出来，所以不用算。
于是莫队应该维护有多少个在当前区间出现了恰好一次的数，然后仅用这些数当贡献。
注意需要特判 $u=LCA$ 或者 $v=LCA$，并且当 $u\neq LCA$ 和 $v\neq LCA$，欧拉区间里不会有 $LCA$，需要额外加上。
这样退化成序列莫队，仍然 $O(n\sqrt q)$。
## P5071 [Ynoi2015] 此时此刻的光辉
~~这是 PR 测速题！~~
首先 pollard rho 质因数分解所有输入的数。
考虑到 $d$ 是积性函数，可以分别计算所有约数的贡献。暴力莫队每一次转移的时间复杂度会为 $O(\ln n)$，总共 $O(n\ln n\sqrt n)$，有点慢。
考虑特判最小的几个质因子，例如 $2\to19$ 的所有质数，直接把转移的最坏需要用的时间减掉很多。这些最小质因子存一个前缀和表就可以。（或者也许能滚动？减少内存用量）
这样在分支线地下的质数就不参与莫队的复杂度，复杂度降为 $O((n+q)\frac{B}{\ln B}+n\frac{\ln v}{\ln B}\sqrt q)$。B=88 挺快。
## P5072 [Ynoi2015] 盼君勿忘
~~我寻思如果这道题今年出直接 n=5e5 卡掉 bitset~~
题意：区间询问所有子序列里（本质不同元素之和）之和。动态模数。
考虑贡献：一个值对区间的贡献等于有多少子序列包含它。
假设已经提取出来这个区间，有 $2^n$ 子序列，$2^{n-c_x}$ 子序列不包含 $x$，于是答案是
$$\sum_{x=0}^{10^5}x(2^n-2^{n-c_x})$$
拆：
$$\sum_{x=0}^{10^5}x2^n-\sum_{x=0}^{10^5}x2^{n-c_x}$$
第一部分比较简单计算，主要看第二部分。
稍微转化：
$$\sum_{d=0}^n2^{n-d}\sum_{c_x=d}x$$
考虑用莫队维护
$$V_d=\sum_{c_x=d}x$$
首先，观察最多只可能有 $O(\sqrt n)$ 个 $d$ 值使得 $V_d$ 非零。这是一个自然根号，可以用鸽子（抽屉原理）解释：
贪心构造，每一次尽量创建一个新的 $d$ 值使得 $c_x=d$，显然最优来从小到大创建 $d$。这些 $d$ 形成一个前缀，叫最大 $D$，需要满足 $\frac{D(D+1)}{2} \le n$。可知 $D=O(\sqrt n)$。
可以用 bitset 维护那些 $d$ 是非零来快速跳。
最后需要对非零的 $V_d$ 快速计算 $2^{n-d}$。暴力就直接 $O(n\log n\sqrt n)$；可以对每一个询问处理出来 $[2^0,2^1,2^2,\dots,2^{\sqrt n}]$ 和 $[2^0,2^{\sqrt n},2^{2\sqrt n},\dots,2^{\sqrt n\sqrt n}]$ 数组，可以 $O(1)$ 找出来任何幂，预处理值需要 $O(\sqrt n)$。
整体时间复杂度 $O(q\sqrt n+n\sqrt q+q\frac{n}{\omega})$。
## 习题
- [P4113 [HEOI2012]采花](https://www.luogu.com.cn/problem/P4113)（166 分）
- [P6782 [Ynoi2008] rplexq](https://www.luogu.com.cn/problem/P6782)（莫队用来平衡复杂度）
# 【Ynoi 序列上的大分块系列】
## 1 未来日记
分块，维护一些块的前缀的出现次数的值域分块。这样查询第 $k$ 可以直接 $O(\sqrt n)$ 查询。
对每一个块维护一个映射。
1. 散块修改直接重构。
2. 对于整块修改 $a$ 为 $b$：
1. 如果 $a$ 没出现，跳过；
2. 如果 $b$ 没出现，进行映射，跳过；
3. 否则暴力重构，由于每一个块至多被重构 $O(\sqrt n)$ 次，时间复杂度正确。
总共时间复杂度 $O((n+q)\sqrt n)$。
## 2 五彩斑斓的世界
这基本上等价于未来日记但是有 批 量 修 改（
考虑 $a$ 替代为 $b$ 过程如何优化。
第一个想法是并查集，但是对值开并查集显然是错误的，因为 $a$ 替代为 $b$ 之后还可以 $c$ 替代为 $a$，这时候并没 $c=b$。于是对数组位置开并查集，因为两个数组位置同一个值之后肯定不会分开。对每一个颜色维护它在数组里的任意一个出现处，想合并 $a$ 和 $b$ 时候可以寻找该位置并进行合并。
由于一些奇怪原理，并查集高度至多为 $1$，时间复杂度保证为 $O((n+q)\sqrt n)$。
## 4 天降之物
考虑序列分块，每一块里面维护某个值的第一个出现位置，某一个值的最后一个出现位置，和两个值之间在块内最小距离。
如果直接维护每一个块需要 $O(n^2)$ 个信息，内存炸。注意一个块里面最多有 $O(\sqrt n)$ 个互异值，所以可以对每一个块维护离散化，只需要维护 $O(n)$ 个信息了。
现在询问就可以模拟，考虑怎么修改。如果在一个块想把 x 修改成 y，有三个情况：
- x 不出现，可以跳过；
- y 不出现，可以修改 x 的离散化值，距离信息不需要修改；
- x 和 y 都出现。在这里可以暴力更新影响的距离（最多有 $O(\sqrt n)$ 个），因为每一次暴力更新这个块里互异值数量减一。每一个块封顶暴力修改 $O(\sqrt n)$ 次，对时间复杂度的贡献仅仅是 $O(n^{3/2})$。
然后讲卡常：
- 优化 1：优化预处理常数。
- 优化 2：直接用数组，不要用 struct 加大常数。
- 优化 3：减少数组访问次数，查找距离的时候保证第一位小于第二维，不要更新太多次。
- 优化 4：重新排列离散化数组维度。
- 优化 5：瞎调块长，选 250。
然后就终于好了。
## 6 末日时在做什么？有没有空？可以来拯救么？
考虑一种别的（无修改）问题：给定序列，如何求序列 $[l,r]$ 最大子段和，如果全局先加上 $x$ 了？修改临时。利用线段树求最大子段和需要维护的信息的思想（SPOJ GSS1）可以构造出来几个关于 $x$ 的函数：
$$\begin{cases}T_{[l,r]}(x)=[l,r]+x\text{ 后区间和}\\P_{[l,r]}(x)=[l,r]+x\text{ 后最大前缀和}\\S_{[l,r]}(x)=[l,r]+x\text{ 后最大后缀和}\\A_{[l,r]}(x)=[l,r]+x\text{ 后最大子段和}\end{cases}$$
我们希望求 $A_{[l,r]}$。对于任意 $m\in[l,r]$，满足 GSS1 信息合并恒等式，可以完全忽略 $(x)$ 部分套原公式。
$$\begin{cases}T_{[l,r]}(x)=T_{[l,m]}(x)+T_{[m+1,r]}(x)\\P_{[l,r]}(x)=\max(P_{[l,m]}(x),T_{[l,m]}(x)+P_{[m+1,r]}(x))\\S_{[l,r]}(x)=\max(S_{[l,m]}(x)+T_{[m+1,r]}(x),S_{[m+1,r](x)})\\A_{[l,r]}(x)=\max(A_{[l,m]}(x),A_{[m+1,r]}(x),P_{[l,m]}(x)+S_{[m+1,r]}(x))\end{cases}$$
发现并不需要求出来 $A_{[l,r]}$ 整体，而可以通过以上方法合并答案。区别在于 $l=r$ 时候：
$$\begin{cases}T_{[l,l]}(x)=a_l+x\\P_{[l,l]}(x)=S_{[l,l]}(x)=A_{[l,l]}(x)=\max(0,a_l+x)\end{cases}$$
考虑建立线段树，线段树 $[l,r]$ 节点保留着四个函数。直接存不可能，**但是**：
1. $T_{[l,r]}(x)$ 可以表示为一个一次函数
2. $P_{[l,r]}(x)$ 和 $S_{[l,r]}(x)$ 均至多取 $r-l+2$ 个**本质意义**不同的值，因为只有 $r-l+2$ 个前缀和后缀
3. 这里本质意义不是为值，而是一个值的一段，其中这一段内值可以为一个依次函数表示
4. 通过一个“加热”过程可以看出来 $A_{[l,r]}(x)$ 也最多有 $r-l+2$ 个本质意义不同的值：$x$ 的最大子段和区间必须包含 $x-1$ 的最大子段和区间，于是每一个位置最多被添加一次
于是可以把这三个函数全抽象为分段函数，对每一段暴力考虑 $\max$ 和 $+$，类似于归并排序。则以上问题 $O(n\log n)$ 或 $O(n\log^2n)$ 解决。
然后你到这个问题来就可以强行上分块，可以做到 $O(n\sqrt{n\log n})$。
1. 散块查询：这没啥好说的，直接暴力查，$O(B)$。
2. 整块修改：直接打上 tag，$O(1)$。
3. 整块查询：对根二分当前 tag 值，$O(\log B)$，，，咦时间复杂度不对。我们可以两个散块修改之间进行离线并且**逐块处理**，因为每一个块的答案独立，可以对这些整块查询按照 tag 排序，然后扫描线扫过去。这样时间复杂度为每一个散块修改 $O(\sqrt n)$，查询均摊 $O(1)$。
4. 散块修改：暴力重构是 $O(B\log B)$，但是发现可以标记永久化而只重构线段树每一层的一个节点，时间复杂度 $O(B)$。
总共时间复杂度 $O((n+q)\sqrt n)$。
## 10 魔法少女网站
在一个块里，访问全局仅会有 $O(\sqrt N)$ 不同的答案，于是考虑 P4118 的套路：逐块处理，线段树维护分段函数。
这个分段函数就是 $f(x)=$ 区间里 $\le x$ 数标为 1，$>x$ 的数标为 0，区间 tag 值是什么。tag 会保存（区间内答案，区间前缀 1 个数，区间后缀 1 个数，区间是否全是 1）这四个东西，可以快速合并 tag 得到答案。
我们可以维护分段函数的段的左端点，访问 $\le x$ 答案时候在分段函数上面二分。线段树叶子节点对应的分段函数就会是 $f(0)=(0,0,0,0)$ 和 $f(a_i)=(1,1,1,1)$。
两个分段函数合并时候会产生的新左端点等于原来的两个左端点序列的归并，可以用双指针同时爬两个分段函数来合并。
线段树节点内的分段函数会存 $|L|$ 个值，其中 $|L|$ 是区间大小。合并是 $O(n)$，所以建立线段树时空是 $O(\log n\sqrt n)$。
考虑最 naive 做法：在一个块的所有询问都二分，每一次在一个块里修改都 rebuild。定义 $q$ 为询问，$m$ 为修改。这样：
- 整块询问 $O(\log n)$，总共有 $O(q\sqrt n)$ 个，对时间复杂度贡献 $O(q\log n\sqrt n)$
- 散块询问 $O(\log^2 n)$，总共有 $O(q)$ 个，对时间复杂度贡献 $O(q\log^2 n)$
- 单点修改 $O(\log n\sqrt n)$，总共有 $O(q)$ 个，对时间复杂度贡献 $O(m\log n\sqrt n)$
- 块初始化 $O(\log n\sqrt n)$，总共有 $O(\sqrt n)$ 个，时间复杂度 $O(n\log n)$
$$O(n\log n+(q+m)\log n\sqrt n)$$
炸 出 翔
我们可以离线，然后已经在逐块处理，可以在一个块内两个修改之间的整块询问对 $x$ 排序，根的询问就可以单调爬了。整块询问降到均摊 $O(1)$。
发现单点修改仅仅会影响 $O(\log n)$ 个节点，更具体仅仅会影响每一层的一个节点。只对这些节点重构达到 $O(B+B/2+B/4+...)=O(B)=O(\sqrt n)$ 的单点修改时间复杂度。
于是做到了一个 $O(n\log n+(q+m)\sqrt n)$ 的巨大常数做法。
## 13 Happy Sugar Life
考虑我们把询问矩形分开来成若干行区间和列区间，怎么计算答案？
| (R1C1) | (R1C2) | (R1C3) |
| ------ | ------ | ------ |
| (R2C1) | (R2C2) | (R2C3) |
| (R3C1) | (R3C2) | (R3C3) |
贡献的对可以分为几类。
1. 对在一个子矩形内，对每一个矩形预处理答案。
2. 对在同一个行区间或者列区间，在这个行区间或者列区间上面求区间逆序对。
3. 对在不同的行区间和列区间，可以做一个二维前缀和统计。
注意第一类会在第二类包含，并且第二类会统计第一类两次，所以需要容斥出来。形式化：
$$S((1,1)\cup\dots\cup(n,m)) = -\sum_{i=1}^n\sum_{j=1}^mS((i,j))$$
$$+\sum_{i=1}^nS((i,1)\cup\dots\cup(i,m))+\sum_{j=1}^mS((1,j)\cup\dots\cup(n,j))$$
$$+\sum_{i=1}^n\sum_{j=1}^m|(i,j)|\sum_{k=i+1}^n\sum_{l=j+1}^m|(k,l)|$$
如果我们按照树套树的子矩形来维护答案的话，可以做到 $O(n\sqrt n)$ 时间复杂度，$O(n\log^2 n)$ 空间复杂度（假设 $q=O(n)$）注意还带树套树的 $O(n\log^2 n)$（属于大常数）。
接下来讲实现细节：
- 内层树套树需要用动态开点线段树实现。
- 更方便来让外层标号为值域，内层标号为位置。
- 内层的每一个树都会对应一个值域区间。对这个值域区间先建立完动态开点线段树的形态以及子树大小，然后再dfs初始化逆序对个数。后者用归并排序。
- 区间逆序对用常数最小的方法，莫队二次离线。
- 1 贡献直接按照初始化的东西求。
- 2 贡献全部离线求。对外层树套树对应的值域区间放上位置区间的询问；对内层树套树对应的位置区间放上值域区间的询问。
- 3 的贡献维护一个子树大小后缀和数组。
接下来讲卡常方法：
- 减少数组询问次数，也就是对 3 时候不要开二维数组，而滚动的维护一个以为数组。
- 减少访问区间逆序对的常数，扔掉长度为 0 或者 1 的逆序对询问区间。
- 搞评测波动
接下来讲卡内存方法：
发现我们现在内存复杂度是 $O(n\log^2 n)$，但是正解是 $O(n\log n)$（貌似可以做到 $O(n)$ 啊 不知道如何做到）。瓶颈在于内层树套树。考虑将 1 和 2 都离线到对应的外层线段树节点上，然后 dfs 外层线段树。1 和 2 之间保留状态大小是 $O(\log n)$，所以对每一个询问都开一个数组没问题。
dfs 到一个外层线段树节点上，建立内层线段树，用完然后把内层线段树的所有关键节点都清零。最重要是现在都不需要动态开点了，大大减少时空常数。最后需要注意我们离线的方法。不应该在每一个线段树节点上方 $(l,r,i)$ 形式的信息，而直接放离线的询问编号，直接把内存应用除以 3.
仍然有继续卡常的余地：
- 整数排序用《P4604 [WC2017]挑战》的基数排序，然后只需要三轮。
- 区间逆序对里的离散化不要用二分，而直接用数组即可，毕竟值域是 $O(n)$。不离散化也不行，区间逆序对需要是 $O(|A|)$ 才能保证整体时间复杂度。
## 14 GOSICK
首先，区间满足某条件（$a\equiv0\pmod b \lor b\equiv0\pmod a$）对个数统计用 [莫队二次离线/扫描线莫队](https://www.luogu.com.cn/problem/P4887)。这题非常良心，对的顺序不影响是否满足条件，只需要修改以上题目的离线统计和转移部分。
我们需要 $O(1)$ 计算这个东西当 $p$ 固定，并且 $O(\sqrt n)$ 从 $p$ 转移到 $p+1$：
$$\Delta(p,x)=\sum_{i=1}^p[a_i\equiv 0\pmod{a_x}\lor a_x\equiv 0\pmod{a_i}]$$
这个可以拆成两个部分：
$$\Delta_1(p,x)=\sum_{i=1}^p[a_i\equiv 0\pmod{a_x}]$$
$$\Delta_2(p,x)=\sum_{i=1}^p[a_x\equiv 0\pmod{a_i}]$$
$\Delta_1$ 等价于 $a_x$ 是多少 $a_i$ 的约数，这个东西可以暴力维护一个数组 $D_i$，计算 $\Delta_1(p,x)$ 查找 $D_{a_x}$，转移到一个新 $p$ 时候，对所有约数 $k$ 增加对应的 $D_k$。转移暴力枚举约数即可。
$\Delta_2$ 等价于 $a_x$ 是多少 $a_i$ 的倍数。第一个想法是用和以上一样的方法，转移时候更新所有小于 $5\cdot10^5$ 的倍数。当 $a_i \ge \sqrt n$ 时间复杂度是正确，但是更小倍数个数就是 $O(n)$ 级别了。需要根号分治特判这个部分。
用朴素莫队二次离线做，特判这个部分看的特别难。考虑一下莫队二次离线本质是怎么用 $\Delta(p,x)$：
1. 计算 $\Delta(p,p)$
2. 计算 $\Delta(p,p+1)$
3. 计算 $\sum(\Delta(p,i):L\le i\le R)$
所以其实 $\Delta(p,x)$ 需要 $O(1)$ 计算这个要求仅仅是用于第三个类型。如果第三个类型可以 $O(\sqrt n)$ 计算出来，也没事。为了让计算简洁，这里默认 $L=1$，如果 $L\neq 1$ 反正可以差分。对以上和进行展开：
$$\sum_{x=1}^R\sum_{i=1}^p[a_x\equiv 0\pmod{a_i}\land a_i<\sqrt n]$$
$$\sum_{x=1}^R\sum_{i=1}^p[a_x\equiv 0\pmod{a_i}][a_i<\sqrt n]$$
$$\sum_{i=1}^p\sum_{x=1}^R[a_x\equiv 0\pmod{a_i}][a_i<\sqrt n]$$
$$\sum_{i=1}^p[a_i<\sqrt n]\sum_{x=1}^R[a_x\equiv 0\pmod{a_i}]$$
$$\sum_{v=1}^{\lfloor\sqrt n\rfloor}\sum_{i=1}^p[a_i=v]\sum_{x=1}^R[a_x\equiv 0\pmod{v}]$$
$$\sum_{v=1}^{\lfloor\sqrt n\rfloor}\left(\sum_{i=1}^p[a_i=v]\right)\left(\sum_{x=1}^R[a_x\equiv 0\pmod{v}]\right)$$
定义：
$$S_1(v,p)=\sum_{i=1}^p[a_i=v]$$
$$S_2(v,x)=\sum_{x=1}^R[a_x\equiv 0\pmod{v}]$$
贡献就等于了：
$$\sum_{v=1}^{\lfloor\sqrt n\rfloor}S_1(v,p)S_2(v,x)$$
由于 $v\in[1,\lfloor\sqrt n\rfloor],p,x\in[1,n]$，只有 $O(n\sqrt n)$ 处 $S_1$ 和 $S_2$ 的值有用，这些预处理出来就可以 $O(\sqrt n)$ 回答第三类型了。从这也可以推广到一，二类型，毕竟哪些仅仅是单点计算。
但是实际上开一个 $O(n\sqrt n)$ 的数组内存和常数都稳稳炸了，所以最好方法是在外层遍历 $v$，每一层处理出来这一层的 $S_1$ 和 $S_2$ 值，然后跑一下这一层对所有莫队转移区间的贡献。
最终时间复杂度 $O(n\sqrt n)$，空间复杂度 $O(n)$。
# 【例题参考代码】
## 数列分块入门 6
没封装
```cpp
#include <bits/stdc++.h>
using namespace std;
#define iter(i, a, b) for(int i=(a); i<(b); i++)
#define rep(i, a) iter(i, 0, (a))
#define rep1(i, a) iter(i, 1, (a)+1)
using vi=vector<int>;
vector<vi> kzlb;
const int th=300;
pair<int, vi::iterator> fin(int kth) {
rep(i, kzlb.size()) {
if(kth < kzlb[i].size()) return {i, kzlb[i].begin()+kth};
kth -= kzlb[i].size();
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n; cin >> n;
vi ar(n+1);
rep(i, n) cin >> ar[i];
int l=0;
while(l != n+1) {
int r = min(n+1,l+th);
kzlb.emplace_back(ar.begin()+l, ar.begin()+r);
l=r;
}
rep(i, n) {
int o, l, r, c; cin >> o >> l >> r >> c;
if(o == 0) {
l--;
auto v = fin(l);
int i = v.first;
kzlb[i].insert(v.second, r);
if(kzlb[i].size() == 2*th) {
kzlb.emplace(kzlb.begin()+i+1, kzlb[i].begin()+th, kzlb[i].end());
kzlb[i].erase(kzlb[i].begin()+th, kzlb[i].end());
}
} else cout << *fin(r-1).second << endl;
}
return 0;
}
```
## [NOI2003]文本编辑器
```cpp
#include <bits/stdc++.h>
using namespace std;
#define iter(i, a, b) for(int i=(a); i<(b); i++)
#define rep(i, a) iter(i, 0, (a))
#define rep1(i, a) iter(i, 1, (a)+1)
#define fi first
#define se second
char inpf[1<<23],oupf[1<<23];
char *inp=inpf,*oup=oupf;
string gl() {
string v;
char tmp=*(inp++);
while(tmp == '\n' || tmp == '\r') tmp = *(inp++);
while(tmp != '\n' && tmp != '\r') { v += tmp; tmp = *(inp++); }
return v;
}
vector<string> kzlb;
const int th=3000;
pair<int,int> gt(int idx) {
rep(i, kzlb.size()) {
if(idx < kzlb[i].size()) return {i, idx};
idx -= kzlb[i].size();
}
return {0, 0};
}
void maintain(int idx) {
if(idx == kzlb.size()) return;
if(kzlb[idx].size() == 0) {
kzlb.erase(kzlb.begin()+idx);
maintain(idx);
} else if(kzlb[idx].size() > 2*th) {
kzlb.emplace(kzlb.begin()+idx+1, kzlb[idx].substr(kzlb[idx].size()-th));
kzlb[idx].erase(kzlb[idx].size()-th);
maintain(idx);
}
}
int main() {
fread(inpf, 1, 1<<23, stdin);
int n = stol(gl()), k = 0;
kzlb.push_back("!");
string d, st;
while(n--) {
istringstream com(gl()); com >> d;
if(d == "Insert") {
int n; com >> n;
st = gl();
while(st.size() != n) st += gl();
auto v = gt(k);
kzlb[v.fi].insert(v.se, st);
maintain(v.fi);
}
if(d == "Move") com >> k;
if(d == "Delete") {
int n; com >> n;
auto v = gt(k); int i=v.fi;
while(n) {
int st=v.se, en=min(st+n,(int)kzlb[i].size());
kzlb[i].erase(st, en-st);
n -= en-st;
i++;v.se=0;
}
maintain(v.fi);
}
if(d == "Get") {
int n; com >> n;
auto v = gt(k); int i=v.fi;
while(n) {
int st=v.se, en=min(st+n,(int)kzlb[i].size());
iter(j, st, en) *(oup++) = (kzlb[i][j]);
n -= en-st;
i++;v.se=0;
}
*(oup++) = ('\n');
}
if(d == "Prev") k--;
if(d == "Next") k++;
// for(string i:kzlb) cout << i;
// cout << endl;
}
fwrite(oupf, 1, oup-oupf, stdout);
return 0;
}
```
## 普通平衡树 加强版
```cpp
// writer: w33z8kqrqk8zzzx33
#include <bits/stdc++.h>
using namespace std;
// begin fast read template by CYJian (source: https://www.luogu.com.cn/paste/i11c3ppx)
namespace io {
const int __SIZE = (1 << 21) + 1;
char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1, __c, qu[55]; int __f, qr, _eof;
#define Gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
inline void flush () { fwrite (obuf, 1, oS - obuf, stdout), oS = obuf; }
inline void gc (char &x) { x = Gc(); }
inline void pc (char x) { *oS ++ = x; if (oS == oT) flush (); }
inline void pstr (const char *s) { int __len = strlen(s); for (__f = 0; __f < __len; ++__f) pc (s[__f]); }
inline void gstr (char *s) { for(__c = Gc(); __c < 32 || __c > 126 || __c == ' ';) __c = Gc();
for(; __c > 31 && __c < 127 && __c != ' '; ++s, __c = Gc()) *s = __c; *s = 0; }
template <class I> inline bool gi (I &x) { _eof = 0;
for (__f = 1, __c = Gc(); (__c < '0' || __c > '9') && !_eof; __c = Gc()) { if (__c == '-') __f = -1; _eof |= __c == EOF; }
for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc()) x = x * 10 + (__c & 15), _eof |= __c == EOF; x *= __f; return !_eof; }
template <class I> inline void print (I x) { if (!x) pc ('0'); if (x < 0) pc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10; while (qr) pc (qu[qr --]); }
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
} using io::pc; using io::gc; using io::pstr; using io::gstr; using io::gi; using io::print;
// end fast read template by CYJian
#define iter(i, a, b) for(int i=(a); i<(b); i++)
#define rep(i, a) iter(i, 0, a)
#define rep1(i, a) iter(i, 1, (a)+1)
#define log(a) cerr<<"\033[32m[DEBUG] "<<#a<<'='<<(a)<<" @ line "<<__LINE__<<"\033[0m"<<endl
#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using ll=long long;
using pii=pair<int, int>;
//#define int ll
const int MOD = 1000000007;
const int sz=1000,th=2*sz;
using vi=vector<int>;
struct Splay {
vector<vi> dt;
Splay(vi q){
sort(all(q));
dt.emplace_back();
rep(i,q.size()){
dt.back().push_back(q[i]);
if(dt.back().size() == sz) dt.emplace_back();
}
if(!dt.back().size())dt.pop_back();
}
int get(int p){
int las=-2e9;
rep(i,dt.size()){
if(las<p&&p<=dt[i].back())return i;
las=dt[i].back();
}
return -1;
}
void ins(int p){
int it=get(p);
dt[it].emplace(lower_bound(all(dt[it]),p),p);
if(dt[it].size()>th){
dt.emplace(dt.begin()+it+1,dt[it].end()-sz,dt[it].end());
dt[it].erase(dt[it].end()-sz,dt[it].end());
}
}
void ers(int p) {
int it=get(p);
dt[it].erase(lower_bound(all(dt[it]),p));
if(!dt[it].size())dt.erase(dt.begin()+it);
}
int kth(int p){
for(vi&v:dt){if(v.size()<=p)p-=v.size();else return v[p];}
}
int clt(int p){
int ans=0;for(vi&v:dt){
if(v.back()<p)ans+=v.size();
else{for(int&i:v)ans+=(i<p);break;}
}
return ans;
}
int pre(int p){
int it=get(p);
auto ps=lower_bound(all(dt[it]),p);
if(ps==dt[it].begin())return dt[it-1].back();
return *prev(ps);
}
int nex(int p){
int it=get(p);
auto ps=upper_bound(all(dt[it]),p);
if(ps==dt[it].end())return dt[it+1].front();
return *ps;
}
};
signed main() {
// ios_base::sync_with_stdio(false); cin.tie(0);
int n=0,m;
gi(n);
gi(m);
vector<int> ar(n);
rep(i, n) gi(ar[i]);
ar.pb(2e9);
Splay sp(ar);
int la = 0; ll sm = 0;
rep1(i, m) {
// cerr << i << ' ';
int op,x;
gi(op), gi(x);
// cin >> op >> x;
x ^= la;
if(op == 1) sp.ins(x);
if(op == 2) sp.ers(x);
if(op == 3) sm ^= (la = (sp.clt(x)+1));
if(op == 4) sm ^= (la = sp.kth(x-1));
if(op == 5) sm ^= (la = sp.pre(x));
if(op == 6) sm ^= (la = sp.nex(x));
// cerr << la << endl;
// sp.dfs(sp.rt); cerr << endl;
// return 0;
}
print(sm);
}
```
## P1972 [SDOI2009]HH的项链
```cpp
// writer: w33z8kqrqk8zzzx33
#include <bits/stdc++.h>
using namespace std;
// begin fast read template by CYJian (source: https://www.luogu.com.cn/paste/i11c3ppx)
namespace io {
const int __SIZE = (1 << 21) + 1;
char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1, __c, qu[55]; int __f, qr, _eof;
#define Gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
inline void flush () { fwrite (obuf, 1, oS - obuf, stdout), oS = obuf; }
inline void gc (char &x) { x = Gc(); }
inline void pc (char x) { *oS ++ = x; if (oS == oT) flush (); }
inline void pstr (const char *s) { int __len = strlen(s); for (__f = 0; __f < __len; ++__f) pc (s[__f]); }
inline void gstr (char *s) { for(__c = Gc(); __c < 32 || __c > 126 || __c == ' ';) __c = Gc();
for(; __c > 31 && __c < 127 && __c != ' '; ++s, __c = Gc()) *s = __c; *s = 0; }
template <class I> inline bool gi (I &x) { _eof = 0;
for (__f = 1, __c = Gc(); (__c < '0' || __c > '9') && !_eof; __c = Gc()) { if (__c == '-') __f = -1; _eof |= __c == EOF; }
for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc()) x = x * 10 + (__c & 15), _eof |= __c == EOF; x *= __f; return !_eof; }
template <class I> inline void print (I x) { if (!x) pc ('0'); if (x < 0) pc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10; while (qr) pc (qu[qr --]); }
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
} using io::pc; using io::gc; using io::pstr; using io::gstr; using io::gi; using io::print;
// end fast read template by CYJian
#define iter(i, a, b) for(int i=(a); i<(b); i++)
#define rep(i, a) iter(i, 0, a)
#define rep1(i, a) iter(i, 1, (a)+1)
#define log(a) cerr<<"\033[32m[DEBUG] "<<#a<<'='<<(a)<<" @ line "<<__LINE__<<"\033[0m"<<endl
#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using ll=long long;
using pii=pair<int, int>;
//#define int ll
const int MOD = 1000000007;
int pre[1<<20], nxt[1<<20], ar[1<<20], lc[1<<20], ans[1<<20];
constexpr int bsize = 1024;
struct qry {
int l, r, id;
const bool operator<(const qry& o) const {
if(l/bsize!=o.l/bsize)return l/bsize<o.l/bsize;
return (l/bsize%2) ? (r<o.r) : (r>o.r);
}
} qs[1<<20];
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n; gi(n);
rep1(i, n) pre[i] = 0, nxt[i] = n+1, gi(ar[i]);
rep1(i, n) {
pre[i] = lc[ar[i]];
nxt[lc[ar[i]]] = i;
lc[ar[i]] = i;
}
int m; gi(m);
rep(i, m) qs[i].id = i, gi(qs[i].l), gi(qs[i].r);
int L = 1, R = 1, s1 = 1, s2 = 0, s3 = 0, s4 = 0;
sort(qs, qs+m);
rep(i, m) {
for(; L-4 > qs[i].l; L-=4) {
s1 += (R < nxt[L-1]);
s2 += (R < nxt[L-2]);
s3 += (R < nxt[L-3]);
s4 += (R < nxt[L-4]);
}
for(; L > qs[i].l; L--)
s1 += (R < nxt[L-1]);
for(; R+4 < qs[i].r; R+=4) {
s1 += (pre[R+1] < L);
s2 += (pre[R+2] < L);
s3 += (pre[R+3] < L);
s4 += (pre[R+4] < L);
}
for(; R < qs[i].r; R++)
s1 += (pre[R+1] < L);
for(; L+4 < qs[i].l; L+=4) {
s1 -= (R < nxt[L]);
s2 -= (R < nxt[L+1]);
s3 -= (R < nxt[L+2]);
s4 -= (R < nxt[L+3]);
}
for(; L < qs[i].l; L++)
s1 -= (R < nxt[L]);
for(; R-4 > qs[i].r; R-=4) {
s1 -= (pre[R] < L);
s2 -= (pre[R-1] < L);
s3 -= (pre[R-2] < L);
s4 -= (pre[R-3] < L);
}
for(; R > qs[i].r; R--)
s1 -= (pre[R] < L);
ans[qs[i].id] = s1 + s2 + s3 + s4;
}
rep(i, m) print(ans[i]), pc('\n');
}
```
## AT1219 歴史の研究
```cpp
// writer: w33z8kqrqk8zzzx33
#include <bits/stdc++.h>
using namespace std;
// begin fast read template by CYJian (source: https://www.luogu.com.cn/paste/i11c3ppx)
namespace io {
const int __SIZE = (1 << 21) + 1;
char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1, __c, qu[55]; int __f, qr, _eof;
#define Gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
inline void flush () { fwrite (obuf, 1, oS - obuf, stdout), oS = obuf; }
inline void gc (char &x) { x = Gc(); }
inline void pc (char x) { *oS ++ = x; if (oS == oT) flush (); }
inline void pstr (const char *s) { int __len = strlen(s); for (__f = 0; __f < __len; ++__f) pc (s[__f]); }
inline void gstr (char *s) { for(__c = Gc(); __c < 32 || __c > 126 || __c == ' ';) __c = Gc();
for(; __c > 31 && __c < 127 && __c != ' '; ++s, __c = Gc()) *s = __c; *s = 0; }
template <class I> inline bool gi (I &x) { _eof = 0;
for (__f = 1, __c = Gc(); (__c < '0' || __c > '9') && !_eof; __c = Gc()) { if (__c == '-') __f = -1; _eof |= __c == EOF; }
for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc()) x = x * 10 + (__c & 15), _eof |= __c == EOF; x *= __f; return !_eof; }
template <class I> inline void print (I x) { if (!x) pc ('0'); if (x < 0) pc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10; while (qr) pc (qu[qr --]); }
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
} using io::pc; using io::gc; using io::pstr; using io::gstr; using io::gi; using io::print;
// end fast read template by CYJian
#define iter(i, a, b) for(int i=(a); i<(b); i++)
#define rep(i, a) iter(i, 0, a)
#define rep1(i, a) iter(i, 1, (a)+1)
#define log(a) cerr<<"\033[32m[DEBUG] "<<#a<<'='<<(a)<<" @ line "<<__LINE__<<"\033[0m"<<endl
#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using ll=long long;
using pii=pair<int, int>;
//#define int ll
const int MOD = 1000000007;
int cnt[100005]; ll glbmx=0;
int val[100005];
struct redaction {
int pos, prevcnt; ll prevmx;
}; stack<redaction> re;
void rollback() {
redaction q = re.top(); re.pop();
cnt[q.pos] = q.prevcnt;
glbmx = q.prevmx;
}
constexpr int N=100005;
constexpr int B=300;
int ar[N<<1];
int n;
void ins(int p, bool side) {
int v = ar[p];
re.push({v, cnt[v], glbmx});
if(!(1 <= p <= n)) return;
cnt[v]++; glbmx = max(glbmx, 1ll*val[v]*cnt[v]);
}
ll ans[N];
vector<pair<int,pii>> buccit[100000/B+5];
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0);
map<int,int> lsh;
int q; gi(n), gi(q);
rep1(i, n) {
gi(ar[i]);
if(!lsh.count(ar[i])) {
lsh[ar[i]] = lsh.size()+1;
val[lsh[ar[i]]] = ar[i];
}
ar[i] = lsh[ar[i]];
}
rep(i, q) {
int l, r; gi(l), gi(r);
if((r-l+1)<=B) {
iter(j, l, r+1) ins(j, 1);
ans[i] = glbmx;
while(re.size()) rollback();
} else buccit[r/B].push_back({l, {r, i}});
}
rep(i, n/B+1) {
while(re.size()) rollback();
int cl = i*B, cr = i*B-1;
sort(all(buccit[i]));
reverse(all(buccit[i]));
for(auto q:buccit[i]) {
while(q.fi < cl) ins(--cl, 0);
int ocr = cr;
while(cr < q.se.fi) ins(++cr, 1);
::ans[q.se.se] = glbmx;
// cout << q.se.se << ' ' << i << ' ' << cl << ' ' << cr << ' ' << ca << endl;
while(ocr < cr) rollback(), cr--;
}
}
rep(i, q) print(ans[i]), pc('\n');
}
```
## SP10707 COT2 - Count on a tree II
```cpp
// writer: w33z8kqrqk8zzzx33
#include <bits/stdc++.h>
using namespace std;
// begin fast read template by CYJian (source: https://www.luogu.com.cn/paste/i11c3ppx)
namespace io {
const int __SIZE = (1 << 21) + 1;
char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1, __c, qu[55]; int __f, qr, _eof;
#define Gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
inline void flush () { fwrite (obuf, 1, oS - obuf, stdout), oS = obuf; }
inline void gc (char &x) { x = Gc(); }
inline void pc (char x) { *oS ++ = x; if (oS == oT) flush (); }
inline void pstr (const char *s) { int __len = strlen(s); for (__f = 0; __f < __len; ++__f) pc (s[__f]); }
inline void gstr (char *s) { for(__c = Gc(); __c < 32 || __c > 126 || __c == ' ';) __c = Gc();
for(; __c > 31 && __c < 127 && __c != ' '; ++s, __c = Gc()) *s = __c; *s = 0; }
template <class I> inline bool gi (I &x) { _eof = 0;
for (__f = 1, __c = Gc(); (__c < '0' || __c > '9') && !_eof; __c = Gc()) { if (__c == '-') __f = -1; _eof |= __c == EOF; }
for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc()) x = x * 10 + (__c & 15), _eof |= __c == EOF; x *= __f; return !_eof; }
template <class I> inline void print (I x) { if (!x) pc ('0'); if (x < 0) pc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10; while (qr) pc (qu[qr --]); }
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
} using io::pc; using io::gc; using io::pstr; using io::gstr; using io::gi; using io::print;
// end fast read template by CYJian
#define iter(i, a, b) for(int i=(a); i<(b); i++)
#define rep(i, a) iter(i, 0, a)
#define rep1(i, a) iter(i, 1, (a)+1)
#define log(a) cerr<<"\033[32m[DEBUG] "<<#a<<'='<<(a)<<" @ line "<<__LINE__<<"\033[0m"<<endl
#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using ll=long long;
using pii=pair<int, int>;
//#define int ll
const int MOD = 1000000007;
const int B = 316;
int seq[500005];
int fir[500005], sec[500005], clo, clo2;
int bg[500005], en[500005];
int fa[500005][19];
vector<int> elist[500005];
void dfs(int u, int f) {
bg[u] = clo2++;
fir[u] = clo++;
seq[fir[u]]=u;
fa[u][0] = f;
rep1(i, 18) fa[u][i] = fa[fa[u][i-1]][i-1];
for(int v:elist[u]) if(v != f) dfs(v, u);
sec[u] = clo++;
seq[sec[u]]=u;
en[u] = clo2;
}
int lca(int u, int v) {
if(bg[u] <= bg[v] && bg[v] < en[u]) return u;
for(int i=18; i>=0; i--)
if(!(bg[fa[u][i]] <= bg[v] && bg[v] < en[fa[u][i]]))
u = fa[u][i];
return fa[u][0];
}
struct qr {
int l, r, lc, i;
const bool operator<(const qr& o) const {
if(l/B != o.l/B) return l < o.l;
return ((l/B)%2)?(r<o.r):(r>o.r);
}
} qrs[500005];
int res[500005], cnt[500005];
int ar[500005], globans = 0;
bool has[500005];
void tognode(int u) {
if(has[u]) {
cnt[ar[u]]--;
globans -= !cnt[ar[u]];
} else {
globans += !cnt[ar[u]];
cnt[ar[u]]++;
}
has[u] ^= 1;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0);
en[0] = 1e9;
int n, q;
while(cin >> n >> q) {
clo = clo2 = 0;
rep1(i, n) {
elist[i].clear();
fir[i] = sec[i] = 0;
bg[i] = en[i] = 0;
cnt[i] = ar[i] = has[i] = 0;
rep(j, 19) fa[j][i] = 0;
}
rep(i, q+1) {
res[i] = 0;
qrs[i].l = qrs[i].r = qrs[i].lc = 0;
}
map<int,int> lsh;
rep1(i, n) {
cin >> ar[i];
if(!lsh.count(ar[i]))lsh[ar[i]]=lsh.size()+1;
ar[i]=lsh[ar[i]];
}
rep(i, n-1) {
int u, v; cin >> u >> v;
elist[u].pb(v); elist[v].pb(u);
}
dfs(1, 0);
// rep(i, 2*n) cout << seq[i] << " \n"[i==2*n-1];
rep(i, q) {
qrs[i].i = i;
int u, v; cin >> u >> v;
int L = lca(u, v);
if(u != L && v != L) {
qrs[i].lc = L;
if(sec[u] <= fir[v]) qrs[i].l = sec[u], qrs[i].r = fir[v];
else qrs[i].l = sec[v], qrs[i].r = fir[u];
} else {
if(u == L) u = v;
qrs[i].l = fir[L]; qrs[i].r = fir[u];
}
// cout << u << ' ' << v << ' ' << L << endl;
}
sort(qrs, qrs+q);
int cl = 1, cr = 0;
rep(i, q) {
while(cr < qrs[i].r) tognode(seq[++cr]);
while(qrs[i].l < cl) tognode(seq[--cl]);
while(qrs[i].r < cr) tognode(seq[cr--]);
while(cl < qrs[i].l) tognode(seq[cl++]);
res[qrs[i].i] = globans + (qrs[i].lc ? (!cnt[ar[qrs[i].lc]]) : 0);
}
rep(i, q) cout << res[i] << '\n';
}
}
```
## P5071 [Ynoi2015] 此时此刻的光辉
代码仅搬主要部分。
```cpp
const int MOD = 19260817;
namespace MillerRabin {
int qpow(int b, int e, int m) {
int ans = 1;
while(e) {
if(e & 1) ans = 1ll*ans*b%m;
b = 1ll*b*b%m;
e >>= 1;
}
return ans;
}
bool test(int n) {
if(n<2 || n%6%4 != 1) return (n|1) == 3;
static int ar[4] = {2, 325, 9375, 28178};
int s=__builtin_ctz(n-1); int d=n>>s;
rep(i, 4) {
int k = qpow(ar[i]%n, d, n); int t=s;
while(k!=1 && k!=n-1 && ar[i]%n && t--) k=1ll*k*k%n;
if(t!=s && k!=n-1) return 0;
}
return 1;
}
}
mt19937 rng;
namespace Factor {
set<int> p;
void mxf(int n) {
if(n == 1) return;
if(MillerRabin::test(n)) { p.insert(n); return; }
auto g = [&](int x){ return (1ll*x*x+1)%n; };
int x = 0, y = 1, pd = 2, tk = 0, tmp;
while(++tk % 10 || __gcd(pd, n) == 1) {
if(x == y) x = rng()%n, y = g(x);
if(tmp = 1ll*(max(x, y) - min(x, y))*pd%n) pd = tmp;
x = g(x), y = g(g(y));
}
int d = __gcd(pd, n);
mxf(d), mxf(n/d);
}
}
map<int,int> wkp;
set<int> sm;
int pw[1<<20];
int inv[3<<20];
int a[100005], lef[100005];
int ba[1<<20], ex[1<<20];
const int bs = 316;
struct qr {
int l, r, i;
const bool operator<(const qr& o) const {
if(l/bs != o.l/bs) return l < o.l;
return ((l/bs)%2) ? (r < o.r) : (r > o.r);
}
} qr[100005];
int ans[100005], smp[100005];
int ps[100005];
int th = 88;
inline void add(int id, int& ca) {
int be = lef[id], en = lef[id+1];
iter(p, be, en) ca=1ll*ca*inv[pw[ba[p]]]%MOD*(pw[ba[p]]+=ex[p])%MOD;
}
inline void del(int id, int& ca) {
int be = lef[id], en = lef[id+1];
iter(p, be, en) ca=1ll*ca*inv[pw[ba[p]]]%MOD*(pw[ba[p]]-=ex[p])%MOD;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n, q; gi(n), gi(q);
inv[0] = inv[1] = 1;
iter(i, 2, n*30+2) inv[i]=1ll*(MOD-MOD/i)*inv[MOD%i]%MOD;
int cn = 0;
rng = mt19937(108616);
rep1(i, n) gi(a[i]);
rep(i, q) gi(qr[i].l), gi(qr[i].r), qr[i].i = i, ans[i] = 1;
rep1(p, th) {
if(!MillerRabin::test(p)) continue;
rep1(i, n) {
ps[i] = ps[i-1];
while(a[i] % p == 0) a[i] /= p, ps[i]++;
}
rep(i, q) ans[i] = 1ll * ans[i] * (ps[qr[i].r] - ps[qr[i].l-1] + 1) % MOD;
}
rep1(i, n) {
Factor::p.clear(); Factor::mxf(a[i]);
int v = a[i];
lef[i] = cn;
for(int p:Factor::p) {
if(!wkp.count(p)) wkp[p] = wkp.size();
ba[cn] = wkp[p];
pw[ba[cn]] = 1;
while(v % p == 0) v /= p, ex[cn]++;
cn++;
}
}
lef[n+1] = cn;
sort(qr, qr+q);
int ca = 1, l = 1, r = 0;
rep(i, q) {
while(r < qr[i].r) add(++r, ca);
while(qr[i].l < l) add(--l, ca);
while(qr[i].r < r) del(r--, ca);
while(l < qr[i].l) del(l++, ca);
ans[qr[i].i] = 1ll * ans[qr[i].i] * ca % MOD;
}
rep(i, q) print(ans[i]), pc('\n');
}
```
## P5072 [Ynoi2015] 盼君勿忘
代码仅搬主要部分。
FastMod 是一个快速摸工具。
```cpp
const int bs = 317;
struct q {
int l, r, p, i;
const bool operator<(const q& o) const {
if(l/bs != o.l/bs) return l < o.l;
return ((l/bs)%2) ? (r < o.r) : (r > o.r);
}
} qr[100005];
int ar[100005], re[100005];
uint64_t vv[100100>>6];
template<typename T>
void process(int wds, T func) {
rep(i, wds) {
if(!vv[i]) continue;
uint64_t cp = vv[i];
while(cp) {
int pos = __builtin_ctzll(cp);
func(i*64|pos);
cp ^= (1ull << pos);
}
}
}
ll mt[100005];
int coun[100005];
int lo[bs+1], hi[bs];
#define rem(aede) { mt[coun[aede]] -= aede; vv[coun[aede]>>6] ^= ((mt[coun[aede]]) ? 0 : (1ull<<(coun[aede]&63))); }
#define ic(aede) { vv[coun[aede]>>6] |= (1ull<<(coun[aede]&63)); mt[coun[aede]] += aede; }
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n, q; gi(n), gi(q);
rep1(i, n) gi(ar[i]);
rep(i, q) gi(qr[i].l), gi(qr[i].r), gi(qr[i].p), qr[i].i = i;
int cl = 1, cr = 0;
sort(qr, qr+q);
mt[0] = 100000ll*100001/2;
vv[0] = 1;
rep(i, q) {
while(cr < qr[i].r) {
int ad = ar[++cr];
rem(ad); coun[ad]++; ic(ad);
}
while(qr[i].l < cl) {
int ad = ar[--cl];
rem(ad); coun[ad]++; ic(ad);
}
while(qr[i].r < cr) {
int re = ar[cr--];
rem(re); coun[re]--; ic(re);
}
while(cl < qr[i].l) {
int re = ar[cl++];
rem(re); coun[re]--; ic(re);
}
int L = cr - cl + 1;
int p = qr[i].p, ans = 0;
lo[0] = 1;
FastMod F(p);
rep1(i, bs) {
lo[i] = lo[i-1]<<1;
lo[i] -= (lo[i] >= p ? p : 0);
}
hi[0] = 1; hi[1] = lo[bs];
iter(i, 2, bs) hi[i] = F.reduce(1ll*hi[1]*hi[i-1]);
process((L>>6)+1, [&](int i){
ans = F.reduce(ans + F.reduce(1ll * F.reduce(mt[i]) * lo[(L-i)%bs]) * hi[(L-i)/bs]);
});
ll v = 100000ll*100001/2;
v %= p; v = v * lo[L%bs] % p * hi[L/bs] % p;
re[qr[i].i] = (v + p - ans) % p;
}
rep(i, q) print(re[i]), pc('\n');
}
```