- \(\sum_{i=1}^{n}\sum_{j=i+1}^{n}dep_{LCA_(i,j)}\)
可转化为：依次统计从 根节点 到 \(i\)
的边权和，统计完后将 根节点 到 \(i\)
的所有边的边权的倍数增加 \(1\)。
- \(f_{m+n}=f_{m-1}\times f_{n}+f_{m}\times
f_{n+1}\)，\(f_{i}\) 表示
斐波那契数列 的第 \(i\) 项。
- 假设当前有 \(n\)
个整数，时刻更改一个数的值，维护乘积，要取模。可以表示为 \(x\times 0^y\)，多一个 \(0\) 就将 \(y\) 增加 \(1\)，少一个 \(0\) 就减少 \(1\)。\(x\)
为其他数的乘积。
- 设 \(G\) 是 \(n \geq 3\) 阶 \(m\) 条边的简单平面图，则 \(m\leq 3n-6\)。
- 逆序对可以转化为二维平面上的点对。对于求一个排列的所有子区间的逆序对数量的最大值，可以转化为扫描线在 \(O(n\log n)\) 的时间内求出。具体的，求出前缀最大值和后缀最小值，然后二分查找每个点能产生贡献的范围，转化为若干矩形，区间加，全局 \(\max\) 即可。
Trick 合集
2025/3/12
OI