Trick 合集

持续更新 ing……

数据结构（Data Structure）

1. 区间查询操作的结果且为 $\text{poly log}$ 做法时：
   • 如果存在较小量且操作具有结合率：考虑倍增或线段树维护。
     [eJOI 2024] 古迹漫步 / Old Orhei

     题意

     给定一个包含 $N$ 个节点 $M$ 条边的有向图（每条边编号为 $1 \sim M$）和一个长度为 $T$ 的序列 $A$（$A_i$ 表示边编号）。需要处理 $Q$ 次操作：

     • 查询操作 ($\texttt{1 L R S}$)：从节点 $S$ 出发，依次检查序列 $A$ 的子区间 $[L,R]$ 中的每个元素 $Z$。若当前节点 $X$ 是编号为 $Z$ 的边的起点，则移动到该边的终点，否则不动。输出最终停留的节点。
     • 修改操作 ($\texttt{2 i K}$)：将序列 $A$ 的第 $i$ 项修改为 $K$。

     数据范围：$N \leq 50$，$M,T,Q \leq 10^5$。

     思路

     观察题目中的较小量是什么？不难发现 $N\le 50$。而且，题目中的操作相当于移动点，如果某个点 $X$ 经过前 $k$ 次操作到达 $Y$，$Y$ 经过后 $k$ 次操作到达 $Z$，则 $X$ 经过总共的 $2k$ 次操作会到达 $Z$。

     这说明，题目中的操作是满足结合率的。也就是说，线段树是可以合并节点的。对于每个节点，维护 $1\sim N$ 每个点经过该节点对应区间后对应的位置。pushup 的时候，直接按上文所说合并即可。
   • 如果不存在较小量且每次操作本质上是合并两个集合（比较罕见）：解决方案本质上是使用广义上的 Kruskal 重构树（或者应该叫做 DSU 重构树？），每次合并两个集合的时候，新建节点，并将两个集合的对应节点连接该点。
     这样的好处在于每两个点的 LCA 记录了这两个点最小加入同一集合的时刻。这对维护区间操作结果有很大的作用。
     花田魔法 (flower)

     题意

     给定长度为 $n$ 的序列 $a$，初始 $a_i=i$。有 $m$ 种魔法：

     • $\tt x_i\ y_i$：$\forall i \in [1,n]\land a_i=x_i$，$a_i:=b_i$。

     接下来有 $q$ 次询问：

     • $\texttt{l r}$：依次施加第 $l,l+1,\dots,r$ 种魔法，序列 $a$ 有多少个极长颜色连续段。

     例如，$a$ 序列为 $1,1,2,2,3$，则极长颜色段为 $[1,1],[2,2],[3]$。

     注意： 每次只是假想地施加魔法，并没有真正的进行，即不同询问之间是独立的。

     数据范围： $1\le n,m,q\le 5\times 10^5$。

     思路

     Hint 1：$O(nq)$ 怎么做？

     考虑对极长颜色段拆贡献，转化为 $a_i\ne a_{i+1}$ 的 $i$ 的数量。

     考虑将每次 $x_i\to y_i$ 看作是一条边，每次导致两个集合变为同一个值，也就是合并两个集合。

     于是，每次 DSU 暴力维护即可。查询判断有多少个 $i$ 和 $i+1$ 不在同一个集合。

     Hint 2：如何用 DSU 重构树描述 Hint 1 中的过程

     考虑每次 $x_i$ 和 $y_i$ 合并的时候，新建一个节点，作为 $x_i$ 和 $y_i$ 的父亲，同时另该节点的颜色为 $y_i$。如果不存在颜色 $y_i$，则新建一个节点，作为 $x_i$ 的父亲。

     注意，这里再表述 $x_i$ 和 $y_i$ 节点的时候，均指最后一次颜色为 $x_i$ 和 $y_i$ 的节点编号。

     这样，在这棵树上，可以很好地通过 LCA 来判断两个点从什么时候开始在同一个集合。

     现在是区间查询，有两个维度（左边界和右边界），扫描线来处理左边界，右边界在 DSU 重构树上处理。

     考虑 $l$ 从 $m$ 到 $1$ 枚举，每次相当于在树上插入首次操作。这是容易的，只需要新建节点 $u$，颜色为 $y_i$，并将 $x_i$ 的父亲定为 $u$，$y_i$ 的父亲定为 $u$，$u$ 的父亲定为原来 $y_i$ 的父亲（如果存在）。

     每次只会更新 $3$ 个点，LCA 只会变化 $2$ 个。因为只有 $x_i,x_i+1$ 和 $x_i-1,x_i$ 的 LCA 发生变化。于是，只需要动态维护 LCA，这里由于每次都是改叶子，所以是可以通过倍增数组做到 $O(\log n)$ 维护的。

动态规划（Dynamic Programming）

1. 分步转移：当 DP 维度中存在多个转移互相独立的维度，每次转移时每个维度同时枚举可以转变成仅枚举一个维度，并用 0/1/... 记录已经转移了哪些。
   跳石头 (stone)

   题意

   给定 $2\times (n+2)$ 的矩形，初始两只脚分别位于第 $0$ 列，终点为两只脚均位于第 $n+1$ 列。

   令 $(i,j)$ 表示左脚在第一排的第 $i$ 个石头上，右脚在第二排的第 $j$ 个石头上，那么你可以进行一次跳跃：选择一对整数 $(k,l),k>i,l>j,a_k=b_l$，然后左脚跳到第 $k$ 个石头上，右脚跳到第 $l$ 个石头上，这次跳跃消耗的体力为 $(k-i)^2+(l-j)^2$。

   试求从起点到终点最小消耗的体力是多少

   数据范围： $n\le 3000$。

   思路

   令 $f_{i,j}$ 表示左脚位于 $i$ 位置，右脚位于 $j$ 位置的最小消耗的体力。

   转移枚举下一次的位置 $k,l$，时间复杂度为 $O(n^4)$。

   不过，不难发现题目斜率优化的形式，只不过二维斜率优化是困难的。于是，考虑左脚、右脚实际上是独立的，可以分部转移。从而优化到一维斜率优化。

   时间复杂度 $O(n^2)$。

字符串（Strings）

1. LCP 和 LCS 可以转化为区间最小值：将字符串按字典序排序，则两个字符串 $i$ 和 $j$ 的 LCP 为 $\text{ord}_i\sim \text{ord}_{j}$ 中相邻两个字符串的 LCP 的最小值（LCS 同理）。
   字符串 (string)

   题意

   给定两个字符串 $a, b$，定义 $f(a, b)$ 为通过以下操作使得 $a = b$ 的最小操作数。如果无法通过操作使它们相同，则 $f(a, b) = 6666$。

   一次操作定义为：选择 $a$ 或者 $b$，选择它的一个子区间 $[l, r]$，将该子区间的所有字符按字典序从小到大排序。

   现在给定 $n$ 个长度相等的字符串 $s_{1}, s_{2}, \cdots, s_{n}$，请计算出 $\sum_{i=1}^{n} \sum_{j=i+1}^{n} f(s_{i}, s_{j})$。

   数据范围： $1 \leq n$，$|s_i| \leq 5 \times 10^5$，$n \cdot |s_1| \leq 5 \times 10^5$，$|s_1| = |s_2| = ... = |s_n|$。

   思路

   观察到，$f(s, t)$ 的值仅有 $4$ 种：

   1. $s=t$：$f(s,t)=0$。
   2. $s$ 排序某个区间能变成 $t$：$f(s,t)=1$。
   3. $\text{sort}(s)\ne \text{sort}(t)$：$f(s,t)=6666$。
   4. $\text{otherwise}$：$f(s,t)=2$。

   考虑将字符串按照 $\text{sort}(s_i)$ 排序，那么只需要考虑每个极长相等段即可。

   于是，计算 $f(s,t)=1$ 的对数，这样用总数减去 $f(s,t)=0$（容易计算）减去 $f(s,t)=1$ 的对数，便是 $f(s,t)=2$ 的对数。

   考虑每个字符串 $s_i$ 的每个单调不降的极长区间 $[l,r]$，只需要计算有多少个字符串与 $i$ 的 LCP 大于等于 $l$，LCS 大于等于 $|s_i|-r+1$。

   将 LCP 和 LCS 转化为区间 $\min$ 之后，不难发现，合法答案在两段区间的交集，将每个字符串变成二元组，这样每次相当于矩阵和。二维偏序，扫描先即可。

   时间复杂度：$O(n\log n)$。

数学

1. 整除分块区间 $[L,R]$ 满足 $2L\ge R$。
2. 数字 $x$ 除 $1\sim \sqrt x$ 下取整两两不同。