Trick 合集

Pigsyy · 2025-07-25 21:11:51 · 个人记录

持续更新 ing……

数据结构（Data Structure）

区间查询操作的结果且为 \text{poly log} 做法时：
- 如果存在较小量且操作具有结合率：考虑倍增或线段树维护。 ::::info[[eJOI 2024] 古迹漫步 / Old Orhei] :::info[题意] 给定一个包含 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。 ::: :::success[思路] 观察题目中的较小量是什么？不难发现 N\le 50。而且，题目中的操作相当于移动点，如果某个点 X 经过前 k 次操作到达 Y，Y 经过后 k 次操作到达 Z，则 X 经过总共的 2k 次操作会到达 Z。
  
  这说明，题目中的操作是满足结合率的。也就是说，线段树是可以合并节点的。对于每个节点，维护 1\sim N 每个点经过该节点对应区间后对应的位置。pushup 的时候，直接按上文所说合并即可。 ::: ::::
- 如果不存在较小量且每次操作本质上是合并两个集合（比较罕见）：解决方案本质上是使用广义上的 Kruskal 重构树（或者应该叫做 DSU 重构树？），每次合并两个集合的时候，新建节点，并将两个集合的对应节点连接该点。
  
  这样的好处在于每两个点的 LCA 记录了这两个点最小加入同一集合的时刻。这对维护区间操作结果有很大的作用。
  
  :::::info[花田魔法 (flower)] ::::info[题意] 给定长度为 n 的序列 a，初始 a_i=i。有 m 种魔法：
  接下来有 q 次询问：
  例如，a 序列为 1,1,2,2,3，则极长颜色段为 [1,1],[2,2],[3]。
  
  注意： 每次只是假想地施加魔法，并没有真正的进行，即不同询问之间是独立的。
  
  数据范围： 1\le n,m,q\le 5\times 10^5。 ::::
  
  ::::success[思路] :::warning[Hint 1：O(nq) 怎么做？] 考虑对极长颜色段拆贡献，转化为 a_i\ne a_{i+1} 的 i 的数量。
  
  考虑将每次 x_i\to y_i 看作是一条边，每次导致两个集合变为同一个值，也就是合并两个集合。
  
  于是，每次 DSU 暴力维护即可。查询判断有多少个 i 和 i+1 不在同一个集合。 ::: :::warning[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）

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

::::info[跳石头 (stone)] :::info[题意] 给定 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。 :::

:::success[思路] 令 f_{i,j} 表示左脚位于 i 位置，右脚位于 j 位置的最小消耗的体力。

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

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

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

字符串（Strings）

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

::::info[字符串 (string)] :::info[题意] 给定两个字符串 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 $。

:::success[思路] 观察到，f(s, t) 的值仅有 4 种：
考虑将字符串按照 \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)。 ::: ::::

数学

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