还是接着分块，之前写太多了，marktext 炸了。

Legendgod’s Blog

  • Δ 带插入全序集维护
题意：维护一个序列，支持（在指定元素后面）插入元素，询问两个元素的先后顺序。
  1. 平衡树

可以暴力维护，复杂度是 O(log⁡n)−O(log⁡n) 。

或者说对于每个平衡树的每个节点钦定一个权值，每次插入的时候根据这样钦定的顺序每个点就有了一个权值，这样我们可以 O(1) 比较。

但是这样对于深度的要求很高，我们用替罪羊树就行了 O(log⁡n)−O(1)。

  1. 块状链表

考虑上面这个 O(1) 很妙能不能加强，我们还是考虑钦定权值，进行分块每块在 [log⁡n,2log⁡n] 的大小之间。

比较元素的时候优先比较块的位置，如果在同一块内在再比较块内的位置。

块内外都用钦定权值维护，但是块的元素数量比较多，如果一直搞链就寄了，所以需要使用平衡树维护，总共有 nlog⁡n 个块，每次插入复杂度是 O(log⁡n) 的，所以是 O(n) 的。

考虑钦定块内元素的权值为前驱和后继权值的平均数。

我们一开始可以特别插入。

发现分裂总共需要 O(nlog⁡n) 次，均摊每次是 O(1)，每次查询是 O(1) 的。

所以复杂度均摊 O(1) 的。

根号分治 & 自然根号

  • Δ 根号分治

例 : 有若干数和为 n ，则最多有 na 个数字大于 a。

若对于某个数可以 O(x) 处理，那我们就以 O(xa) 的复杂度保证了其余数都 ≤a。

看到和，先想能不能根号分治。

看到图先考虑生成树和点的度数。

  • 题意 : 维护一个 n 个点 m 条边的无向图，支持下列两种操作 :

  • 将点 u 的权值 +y。

  • 查询与 u 相连的点的权值和。

点的度数和是 m，考虑对于度数 >m 的点修改的时候计算贡献，然后对于另外的点暴力计算贡献。

题意：维护一个长度为 n 的序列 A 支持下列操作：

  • 单点修改。

  • 查询 ∑i=1n[i≡y(modx)]Ai。

考虑对于 x>n 的部分直接暴力做，小于的部分预处理。

  • Δ 和中的不同数

有若干个数和为 n，不同的数个数为 n 个。

1+2+3+⋯+x=O(x2)。

  • Δ 复杂度与 min 相关的询问

有 m 个集合，大小分别为 S1,S2,S3,⋯,Sm 设 n=∑i=1mSi。

有 q 次对询问，处理询问 (x,y) 的复杂度为 O(min(Sx,Sy))。

如果询问记忆化，总的复杂度为 O(nq)。

将 S 从大到小。

选择最大的 q 个不同的询问，考虑复杂度的和为 O(∑i=1qSi×i)。

考虑对于 q 个复杂度不同的询问，第 i 个最多只能贡献 i 次。

最差情况 S 是 O(q) 个 O(nq)，复杂度是 O(nq)。

  • Δ 广义 SAM 上的一个算法

对于广义 SAM 定义 sizi 表示 parent 树子树内串的种类数。设模板串集合为 S，设 n=∑|Si| ，有结论 ∑usizu 是 O(nn) 级别的。

考虑对于 |Si|≥n 的情况，其贡献最多是 n，因为串的数量少于 n 所以复杂度的贡献是 O(nn)。

对于 |Si|<n 的情况，其贡献最多为 n×max(|Si|)，所以复杂度是 O(nn)。

对于字符串的我们下个专题再说 /qd