我的日志

SongShouqian · 2025-04-27 15:59:19 · 个人记录

2025年秋季

2025-11-24

【语言基础】

cerr<<...

这个东西功能类似 cout，不同的是它总是输出到控制台（即使开了 freopen）。因此，它可以在使用文件读写的情况下比较方便的用来调试。

2025-11-22

【算法基础】/【二分】/【二分答案】

二分答案是为数不多可以改变问题性质 [最优化->存在性] 的做法。后者往往比前者更好处理，能引导你从截然不同的角度思考问题。比如 CSP-S 2023 T4。

2025-11-20

【杂项】/【哈希】

在维护序列或集合时，如果存储它的空间复杂度过大，或者对其进行操作的时间复杂度过高，而我们维护该序列、集合的目的只是为了比较它与另一个序列、集合是否相同，且操作不需要用到序列、集合原来的状态（这样才能用哈希简化，比如说加法），那么我们就可以考虑用哈希维护这个序列。
- 更具体来说，可以给每个元素赋一个随机权值（不一定需要进制，除非你需要截取其中的子段），像 CSP-S 2022 T3 那样。
- 参见：2025-08-26 第 1 条
^\text{DMYOJ-3451}

2025-11-18

【算法基础】/【前缀和 & 差分】/【二维/多维前缀和】

求二维前缀和（原数组记作 a，前缀和数组记作 A）数组时，我们一般采用容斥原理：
A_{i,j}=a_{i,j}+A_{i-1,j}+A_{i,j-1}-A_{i-1,j-1}
但是如果要求更高维度的前缀和数组（k 维），这样就不够方便了，因为求每个元素都需要用到多达 2^k 项，总的复杂度就是 {\rm O}(2^k|a|)：
A_{i_1,\dots,i_k}=a_{i_1,\dots,i_k}+\sum_{S\subseteq\{1,\dots,k\},S\neq\varnothing}(-1)^{|S|+1}A_{i_1-[1\in S],\dots,i_k-[k\in S]}
相比之下，有一种更快的方法——逐维前缀和，总的复杂度只有 {\rm O}(k|a|)：

依次枚举 k 个维度，对于每个维度，对所有 a 中元素在这一维上做一维前缀和。伪代码如下：
枚举维度\,d\\\qquad从小到大枚举\,A\,中下标\,[i_1,\dots,i_k]\\\qquad\qquad A_{i_1,\dots,i_k}\leftarrow a_{i_1,\dots,i_k}+A_{i_1,\dots,i_{d-1},i_d-1,i_{d+1},\dots,i_k}
^\text{DMYOJ-3447}
【其它】

有一些问题要求，给定一个有若干位不确定的二进制数（例如1?0?10?0），对所有与它匹配的二进制数（10001000,10001010,10011000等 8 个数）进行批量操作（如：将一个数组中所有匹配二进制数的位置的权值加上 1）。

可以将这样的问题放到一个坐标值域 \{0,1\} 的 k 维空间里，把上面所说的批量操作变为空间里的矩形操作。（但因为维度可能很高，建议从坐标角度分析问题，详见下面的笔记）

^\text{DMYOJ-3447}
【其它】

遇到高维空间（三维以上）里的问题，不建议从空间角度分析问题（不要尝试在脑子里想什么超立方体，高维的东西对我们三维的大脑来说还是太复杂了），而应该从坐标的角度下手。比如，k 维空间里的一个超立方体一定对应一个二元组数组 (l_1,r_1),(l_2,r_2),\dots,(l_k,r_k)，这个超立方体可以看成所有 \forall i,\,x_i\in[l_i,r_i] 的点的集合。

^\text{DMYOJ-3447}

2025-11-17

【其它】/【拆贡献】
\quad\sum_i\max\{S_i\}\\=\sum_i\sum_v[\max{S_i}\geq v]\\=\sum_v\sum_i[\max{S_i}\geq v]
然后用数据结构等其他方法优化 \sum_i[\exist\max{S_i}\geq v]。

^\text{DMYOJ-3444}
【数据结构】/【线段树】/【线段树二分】

线段树二分也可以在线段树的一段前（后）缀上进行，复杂度也是单次 {\rm O}(\log n)（但常数比整个序列的线段树二分稍大）。代码如下：
```
int find(int x,int p,const at&v){ // 找到 p 及之前的区间上大于等于 v 的最靠后的位置
if(tree[x].val<v){ // 这里不能省！
    return -1; // -1 表示没找到
}
if(L==R){
    return L;
}
int mid=(L+R)>>1;
if(p<=mid){
    return find(ls,p,v);
}
int res1=find(rs,p,v);
if(res1!=-1){
    return res1;
}
return find(ls,mid,v);
}
```
类似地，即使要二分的区间左右边界都不在序列的两端（不是前后缀），也是可以线段树二分的。不过这种情况应该不多。

这样的前后缀线段树二分可以解决“带动态修改的元素前后首个大于位置查询（也就是单调栈用来解决的问题）”之类的问题。

^\text{DMYOJ-3444}

2025-11-10

【图论】/【树上问题】/【树链剖分】

下面几类问题（操作可逆）看似要用树剖，但往往可以用好写且复杂度更优秀的方式解决：
- 单点修改，子树求和\ 子树在 DFS 序上是一段连续的区间，所以问题转化为 DFS 序上单点修改、区间查询。用树状数组即可。
- 子树修改，单点求和\ 和上面类似，用差分树状数组即可。
- 单点修改，路径求和\ 首先考虑如何查询一个点到根节点的路径。\ 可以发现，一个点被修改之后，只会对这个点为根的子树内的点的路径产生贡献。于是我们对每个点直接维护它到根节点的路径的和，问题转化为“子树修改，单点求和”。最后，对于普通路径 (u,v)，将其拆成对节点 u,v,{\rm dis}(u,v) 到根节点路径的查询即可。
- 路径修改，单点求和\ 和上面类似，先把普通路径拆成到根节点的路径，然后用树上差分将问题转化为“单点修改，子树求和”。
- 离线问题（先操作，全部操作完了再查询）\ 通常可以树上差分解决。
一句话概括：凡是区间上不需要用线段树解决的问题，搬到树上（把子树、路径都看成区间）通常也不需要树剖。

^\text{洛谷-P14363}
【专题】/【偏序与数点】

常规的离线静态二维数点问题是这样的：\ 给定 n 个二元组 (x_i,y_i)。有 q 组询问 (a_j,b_j)，对于每个询问求有多少 i 满足 x_i\leq a_j 且 y_i\leq b_j。\ 对询问按 a_j 排序离线后使用树状数组可以做到 {\rm O}((n+q)\log n) 的时间复杂度。

我们可以把这个问题拓展到树上：\ 给定两棵 n 个节点的有根树 T_1,T_2，每棵树的节点编号都为 1~n。有 q 组询问 (a_j,b_j)，其中 a_j,b_j\in[1,n]。对于每个询问求有多少 i 满足：在 T_1 上，i 在 a_j 到根的路径上；在 T_2 上，i 在 b_j 到根的路径上。\ 回顾一下常规离线二维数点的做法，其本质上是对于每个相同的 a_j，用数据结构维护在 a_j 这一维下合法的所有点的 b_j 的情况（这样问题就变成了一维）。在树上，也可以用类似的方法解决问题：对询问按 a_j 在 T_1 的 DFS 序排序离线，对于每个 a_j，用树状数组维护它在 T_1 中到根的路径上所有点在 T_2 中对应点的位置信息（单点修改，路径查询，详见下一条笔记）即可。

^\text{洛谷-P14363}
【字符串】/【字符串哈希】

很多人觉得字符串哈希能替代大部分算法解决字符串问题。实际上，下面几类问题是不适合用字符串哈希做的：
- 多串匹配（一般使用 AC 自动机；如果用哈希，那么复杂度可达 {\rm O}(nL)，一般是没法接受的）
- 非匹配子串统计问题（一般用 SA）
当然，字符串哈希在单串匹配、求 LCP 等问题上表现是比较优秀的，并且好写。所以在遇到这些问题的时候，可以优先考虑。

^\text{洛谷-P14363}

2025-11-08

【语言基础】/【C++ 标准库】/【STL 容器】/【关联式容器】

注意！使用 multiset<Key>::erase(const Key& key) 删除元素时，所有与 Key 相等的元素都会被删除！

如果想只删除一个，可以在中间套一个 find()，把erase() 的参数转变成指针。即multiset<Key>::erase(multiset<Key>::find(const Key& key))。
【语言基础】

std::advance( InputIt& it, Distance n )

的作用是将迭代器 it 往后挪 n 个位置（n 可以为负）。

它可以实现对 set、map 等不支持直接加减的迭代器进行加减操作（但复杂度为线性）。

2025-11-06

【杂项】/【双指针】

双指针常常用来处理这样的序列子区间合法性查询（或统计）问题：
1. 便于加入和删除元素
2. 子区间的合法性随元素的加入而具有单调性（例如，若一个子区间是合法的，那么包含这个子区间的子区间（或被这个子区间包含的子区间）也是合法的）
在这样的“求最短/最长合法区间长度”的问题中，双指针的复杂度往往比二分答案更优（少一个 \log）。

^\text{DMYOJ-3403} ^\text{DMYOJ-3404}

2025-11-04

【其他技巧】

在与给定矩阵有关的问题中，如果可以用一些操作将给定矩阵（n\times m）行列反转并使答案不变，那么应该将 n>m 的矩阵行列反转，也就是将矩阵宽、高的大小关系确定下来（n\leq m）这样不仅更有利于理清思路，在题目对 nm 的上界做了限制（记作 nm\leq K）的时候，还有优化复杂度的作用（例如，一个 {\rm O}(n^2m) 的算法，我们通过调整矩阵让 n 取较小的那一个，实际复杂度就能只有 {\rm O}(K^{1.5})）。

2025-10-30

【数学】/【数论】/【分解质因数】

对于质数 p 和正整数 a，记 F(p,a) 为满足 p^y\mid a 的最大非负整数 y。则对于非负整数 x：
F(p,x!)=\left\lfloor\frac x p\right\rfloor+\left\lfloor\frac x {p^2}\right\rfloor+\left\lfloor\frac x {p^3}\right\rfloor+\dots
^\text{WWOJ-91}
【动态规划】/【状压 DP】

三进制的状压 DP，不仅难写，而且取出某一位时只能用除法和取模，常数比二进制状压的位运算高得多。所以，如果空间充裕，可以索性把三进制改成四进制（也就是用两位描述一个元素的状态）。

^\text{WWOJ-92}
【其他技巧】

看下面这一类问题：给定数轴上 n 个区间，第 i 个区间长度为 k_i。要求第 i 个区间的左端点位置大于等于 x_i，且大于等于第 i-1 个区间的右端点位置。k_i 和 x_i 是动态的，可以通过操作修改。现在要实现快速（单次 {\rm O}(n) 以下）求出每个区间左端点位置的最小值（或求 [区间 i 的左端点最小值相对 x_i 的偏移量] 的最大值）。

解决这个问题需要利用这样一个性质（请自证）：若将区间 i 左端点位置的最小值记作 L_i，则：
L_i=\max_{j=1}^{i}\left\{x_j+\sum_{t=j}^{i-1}k_t\right\}
这个式子将 L_i 表示了出来，这样就不用每次 {\rm O}(n) 从左到右模拟每个区间对右边区间的“向右推动”了。再搭配一些维护最大值的数据结构就可以解决上面的问题了。

类似的，如果问题是“左端点位置大于等于 x_i 且小于等于第 i-1 个区间的右端点位置，求左端点最大值”，方法也是类似的。

^\text{DMYOJ-3286} ^\text{WWOJ-93} （其实我第一次见到这个技巧是在去年 CSP 集训第一天的 T2，名叫 hire）

2025-10-29

【数学】/【组合数学】/【排列组合】/【二项式定理】

二项式定理可以消掉一个 \sum，对降低复杂度非常有用。所以再次强调，推式子的题目里一定要对形如 \sum_{i=0}^n\binom n i x^i 这样的式子特别敏感！更确切地讲，只要看到 \sum_{i=0}^n 和 \binom n i 这两个东西在一起，就可以往二项式定理想了。
- 因为你永远不知道等待你的式子会有多复杂、多恶心……比如下面这个：（除了 x_0,x_1 外所有值都是已知数）^\text{DMYOJ-3387}

\begin{aligned}&\sum_{a_0=0}^{a_1}\sum_{b_0=0}^{b_1}(-1)^{a_0+b_0}\binom{a_1}{a_0}\binom{b_1}{b_0}(k+1)^{a_1b_2+b_1a_2-a_1b_1}\left(\frac k{k+1}\right)^{a_0b_2+b_0a_2-a_0b_0}\\=&(k+1)^{a_1b_2+b_1a_2-a_1b_1}\sum_{a_0=0}^{a_1}(-1)^{a_0}\binom{a_1}{a_0}\left(\frac k{k+1}\right)^{a_0b_2}{\color{red}\sum_{b_0=0}^{b_1}(-1)^{b_0}\binom{b_1}{b_0}\left(\frac k{k+1}\right)^{(a_2-a_0)b_0}}\\=&(k+1)^{a_1b_2+b_1a_2-a_1b_1}\sum_{a_0=0}^{a_1}(-1)^{a_0}\binom{a_1}{a_0}\left(\frac k{k+1}\right)^{a_0b_2}{\color{red}\left[-\left(\frac k {k+1}\right)^{a_2-a_0}+1\right]^{b_1}}\end{aligned}

~~（光是打出上面那个式子的 \KaTeX 就用了 580 个字符）~~

【语言基础】

在遇到需要对答案取模的时候，建议定义一个新结构体类型，把所有运算符都重载成模意义下的运算，并且把所有和计算答案有关的变量都改成这种类型。

typedef long long ll;
const ll P=998244353;
struct modint{
  ll val;
  friend modint operator+(const modint&x1,const modint&x2){
      return modint{(x1.val+x2.val)%P};
  }
  friend modint operator-(const modint&x1,const modint&x2){
      return modint{(x1.val-x2.val+P)%P};
  }
  friend modint operator*(const modint&x1,const modint&x2){
      return modint{x1.val*x2.val%P};
  }
  friend modint qpow(modint a,ll b){//注意指数不能对 P 取模
      modint res={1};
      for(;b;b>>=1,a=a*a){
          if(b&1){
              res=res*a;
          }
      }
      return res;
  }
  friend modint operator/(const modint&x1,const modint&x2){
      return x1*qpow(x2,P-2);
  }
};

这样，把所有可能需要取模的变量都改成 modint 型，可以在遇到复杂式子时节省代码和检查时间。

比如，如果将上一条笔记里那个长式子（最后一行）的计算过程写成代码，如果不用modint，那么要写这么长：

sum=0;
for(int a0=0;a0<=a1;++a0){
  if(a0&1)sign=-1;
  else sign=1;
  (sum+=
      qpow((-qpow(k*qpow(k+1,P-2)%P,a2-a0)+P+1)%P,b1)
      *qpow(k*qpow(k+1,P-2)%P,1ll*a0*b2)%P
      *C(a1,a0)%P
      *((sign+P)%P)%P
  )%=P;
}
(sum*=qpow(k+1,1ll*a1*b2+1ll*b1*a2-1ll*a1*b1))%=P;

如果改成 modint，至少可以少写 13 个 P。

2025-10-28

【图论】\ 【其他技巧】\ ^\text{WWOJ-77} ^\text{WWOJ-89}

看下面两道例题：
1. ^\text{WWOJ-77}给定一张图的 n 个点和两个边集 E_1,E_2，问能否选出 E_2 的一个子集 E'_2 ，使 E_1 与 E'_2 中的所有边（可重）加入到图中后，所有点的度数都是偶数。
2. ^\text{WWOJ-89}给定一张无向图，要求给每条边定向，使每个点的入度都是偶数。（这题寒假里好像还做过）
解决这类问题，容易发现每条未确定的边都有两种状态（1.E_2 中的边选还是不选；2.边 (u,v) 指向点 u 还是点 v），且这条边连接的两点都满足在边的两种状态下度数奇偶性相反。于是问题等价于：

给定一张无向图，每个点初始有点权 0 或 1。现在你可以做若干次操作，每次操作选择一条边，将这条边连接的两点点权反转（异或 1）。问能否通过若干次操作将所有点点权变成 0（或变成 1，方法是类似的）。

我们发现操作相当于把点权为 1 的点沿一条边移动一步，如果碰到了另一个点权为 1 的点，则两点抵消。还发现一个性质：操作不改变点权为 1 的点的个数的奇偶性。

于是我们就有了以下做法：对每个边的连通块求出 DFS 树，并把所有点权为 1 的点一路往上移动到根。如果最后还剩 1 个点没有被抵消，那说明此连通块内的点权为 1 的点个数为奇数，无论怎么操作都不能把它变为 0。否则，所有的点一定都被抵消，得到的是一个合法的方案。

当然，也可以转化为二进制异或问题，用线性基做——但是复杂度不如这种做法优秀。
【其他技巧】\ ^\text{DMYOJ-3385}

有这样一类问题：

有 n 个元素，每个元素有一种颜色。现在你要将一些元素两两配对，要求每次配对的两个元素颜色不相同。（元素不能重复使用）问最多能配出多少对。

对于 n 是偶数的情况：\ 如果存在一种颜色，其对应元素数量超过 n 的一半（即：这种颜色是绝对众数），那么显然，只能将其他颜色的元素全部和这种颜色相配对，剩下的就配不了。\ 但如果所有颜色的元素数量都不超过 n 的一半，那么就一定可以把所有元素都配完。方法是每次挑元素数量最多的两种颜色配。（用反证法自证）

对于 n 是奇数的情况，显然，至少有一个元素配不了。可以证明，把元素数量最多的颜色（如果有多个就任选一个）丢掉一个元素，剩下的元素按偶数情况处理，一定是最优的。

2025-10-16

【专题】/【括号序列】\ ^\text{WWOJ-57}

在与括号匹配有关的问题中，在从前往后给右括号配左括号的时候，完全不需要考虑它最终配的是哪个左括号（只要这不是题目求的）。比如说 ((()中，你完全可以认为第 4 位的右括号配的是第 1 位的左括号。

这是因为，在遇到右括号的时候，我们关心的只是“还剩下多少个可供匹配的左括号”。无论哪个左括号被匹配掉，剩下的左括号数量变化都是一样的（减少 1）。

2025-10-13

（啊……好久没在这儿写过总结了）

【算法基础】/【递归 & 分治】

下面这种分治算法的总时间复杂度都是 {\rm O}(n^2) 的（其中 k 是大于等于 2 的正整数）：
- {\rm T}(n)={\rm O}(n^2)+k{\rm T}(\frac n k)
【算法基础】/【贪心】\ ^\text{DMYOJ-3353}

众所周知，比较两个字符串 s 和 t（或序列）的字典序时，我们从前往后一位位扫，一旦碰到一位 i 使得 s_i 比 t_i 小，那么无论这两个串后面如何，s 的字典序一定排在 t 之前。

这个过程，本质上和贪心很相似。这条性质也就意味着，在“最小化序列字典序”的问题中，往往会采取贪心策略，操作一段序列时，优先保证序列最前面的元素尽量小。

2025-09-02

【专题】/【懒标记】^\text{DMYOJ-3282}

在用打标记批量修改一个集合内的元素时，如果要将一个新元素加入当前带标记的集合，那么比起用标记更新集合内的所有元素，更优的做法是 调整新加入的元素，让它适应集合原有的标记。

更具体地说，只要修改操作是可逆的（操作记作 \oplus，逆运算记作 \ominus），那么在将元素 a 加入集合时，如果集合此时的标记是 t，那么将 a\ominus t 加入集合就能避免对集合内原有的大量元素逐个进行 \oplus t 操作。

2025年暑期

2025-08-29

【数据结构】/【线段树】

动态开点线段树支持值域非常大的情况。在值域大的情况下，即使是静态区间有时也要采用动态开点线段树维护。详细点说：

假如你想要维护一个（或若干）静态数组，并且要求快速查询数组中一段连续区间的信息并（和、最大值等）。

一般情况下，因为数组是静态的，所以对每个数组使用前缀和、ST 表等即可解决；

但如果数组总长度很长，但数组中总共的有效元素数量 m 不多（有效元素指的是，除了这些元素外，其余元素都是一个常数，通常是 0）的时候，由于长度长，所以不能用上面的方法（{\rm O}(n) 的时空复杂度会炸）。这种情况下，请使用动态开点线段树维护所有有效元素。其复杂度为 {\rm O}(m\log n)。
- 例如：^\text{洛谷-P4556}中，我们要为每种颜色（原题中的“救济粮类型”）维护一个长度为 n 的差分数组。数组的总长度是 \text{O}(n^2) 的，不能直接维护；但其中的非 0 元素总共只有 \text{O}(m) 个。所以我们考虑用动态开点线段树，再进一步用线段树合并求解。
【语言基础】

不要把函数的形参变量类型随便设成const Type&x！

你可能以为，这样在函数调用期间，这个x的值就不会变化了；但实际上，const只代表你不能通过x=...的方式给x赋值，由于x是引用变量，如果在函数调用期间x引用的东西发生了变化，那么x也会发生变化！

（我之所以喜欢这么写，还是因为某个大佬告诉我这样比较快……）
【算法基础】/【贪心】

这样一类问题：

有 n 个任务，第 i 个任务有完成耗时 x_i 和截止完成时间 t_i。你可以选择在 [0,t_i-x_i] 的一个时间点开始的一段长度为 x_i 的时间段里完成任务 i。任务一旦开始做就必须做完；同一时间只能做一个任务。^\text{洛谷-P2949} ^\text{洛谷-P4053}

（这一类问题中最简单的问题：）问是否存在一种行动方案能够完成所有这些任务。

不难发现，把所有任务按 t 排序后，从时间点 0 开始从前往后依次做（做完一个，立即做下一个）一定是最优的行动方案。（可以用邻项交换法证明）这也是一种经典的贪心策略。

2025-08-28

【字符串】/【后缀数组 (SA)】

后缀数组是用于处理字符串内不涉及指定子串匹配的子串统计和查询问题的结构。

例如：
1. 求两个后缀的 LCP（最长公共前缀）
2. 求字符串中第 k 小的子串（无论重复出现的子串算一次还是算多次，都能做）
3. 求出现次数至少为 k 的最长子串长度
换言之，SA 解决的问题中，统计和查询的对象往往是给定字符串子串的全部（而不是指定的一个或几个子串）。

当然，指定子串匹配用 SA 也能做，但是更适合采用更好写、跑得快的 KMP、AC 自动机等。

2025-08-27

【其他技巧】\ 【数据结构】/【线段树】

我们都知道线段树是处理复杂“单点修改/区间查询”问题的首选。那如果问题是它的弱化版“单点修改/整体查询”呢？（也就是说，每次查询的区间一定都是整个序列）

情况分两种：
1. 修改后整个序列的信息一定只和修改前序列的信息和这次修改的信息有关\ 也就是说，修改之后，对序列信息产生贡献的新元素，只有可能是被修改的这个元素自己。这种情况下使用线段树维护所有子区间的信息是完全没必要的，只需要维护整个序列的信息，每次直接在上面做修改就行。\ 例：每次将序列中某元素增加一个非负整数，要求维护整个区间的最大值。
2. 仅靠修改前序列的信息和这次修改的信息，无法得出修改后序列的信息\ 也就是说，可能有一些原本对整个序列无贡献（且不在这一轮被修改）的元素，在修改之后对序列产生了贡献。因此想要更新整个序列的信息，必须重新算一遍。\ 这种情况下请老实地使用线段树。\ 例：每次将序列中某元素增加一个可能为负的整数，要求维护整个区间的最大值。
【语言基础】

c++14中，两个bool变量相加相减时，程序会自动将其转化为int类型。因此，两个bool变量相加相减是可以得到 2 或 -1 的。

而如果尝试将int类型的值a赋给bool类型的值，则a会被自动视为(a!=0)。

无论如何，在尝试对bool进行int的算术运算的时候，还是建议先将其手动转化为int类型，避免潜在的麻烦。

2025-08-26

【杂项】/【哈希】

谨记：哈希的作用是能够在较小的时间、空间内维护序列、树、集合等难以快速比较的元素，并判断两个元素是否相同。

如果我们要维护序列或集合时，存储它的空间复杂度过大，或者对其进行操作的时间复杂度过高，而我们维护该序列、集合的目的只是为了比较它与另一个序列、集合是否相同，那么我们就可以考虑用哈希进行维护了。^\text{CodeForces-1794E}
【图论】/【网络流】/【上下界网络流】\ 【图论】/【网络流】/【费用流】/【有负圈的费用流】

上下界网络流和负权费用流中的技巧总结出来就是以下两点：
1. 通过把边与超级源汇相连再跑最大流，我们可以实现“一条边必须流一定量的流量”；
2. 通过建超级源汇之后再建反向边，我们可以实现“一条边默认流了一定量的流量，但可以撤销掉其中的一部分”。
把这两条技巧加以拓展，我们就能求解一些更复杂的问题，如“带负环的有源汇最小费用最大流”“带负环的上下界最小费用流”等。

2025-08-25

【字符串】/【AC 自动机】

AC 自动机的 \rm fail 树上，每个节点的父亲在字典树上的深度一定是比这个节点要小的。也就是说，如果 \rm fail 树上的每条边都由父亲指向儿子，那么字典树的 BFS 序是 \rm fail 树的一个合法的拓扑序。

因此，如果要在 \rm fail 树上进行递推（例如：求一个节点子树的信息并或一个节点到根路径的信息并），不必把这棵树每个节点的儿子处理出来再用常规方式（从根往下 DFS）递推，可以直接按照字典树的 BFS 序处理。^\text{CodeForces-1202E}

2025-08-24

【其他技巧】\ 【数据结构】/【链表】\ 【数据结构】/【并查集】

我们知道，对于“先进行 m 次区间修改，修改完后再进行若干次区间查询”的问题，如果修改操作是加减等可逆的运算，那么可以用前缀和、差分解决；那如果修改操作是“跟一个数 x 取最大值/最小值（以下称‘最优值’）”呢？

如果问题在区间上，可以把所有修改区间按 x 从优到劣排序，然后对于每次询问，将区间中还未求出答案（还未删除）的元素更新答案后删除。这样每个元素最多只会被更新一次答案。^\text{洛谷-P2934}

删除操作可以使用链表；也可以使用并查集，将所有删除的元素与它的下一个元素合并，这样可以快速求出每个元素之后第一个未删除的元素（也就是该元素所在的并查集连通块内最靠后的元素）。

时间复杂度为 O(n+m\log m)。

此问题也可以扩展到树上。不过在树上不宜使用链表（因为删除一个节点需要改变每个子节点的状态）。

此题也启示我们：如果在用链表维护一个序列的过程中只有删除操作，那么也可以用并查集维护该序列。相比于用链表，这么做还可以快速求出任意时刻任意（被删除的）元素后第一个未被删除的元素的位置。
【图论】/【最短路问题】/【最短路】

在单源最短路问题中（假设从起点到所有点的最短路都是唯一的），如果将起点到每一个点的最短路所经过的边都标记为关键边（即：将每个点向对其进行最后一次松弛操作的点连一条关键边），那么所有的关键边会构成一棵树（显然的）。

很多单源最短路的变种问题都可以放在这棵树上考虑。（如^\text{洛谷-P2934}：对于每个点，求删除从起点到该点的最短路上的最后一条边后，新图中起点到此点的最短路长度）

2025-08-14

【图论】/【树上问题】

对于任意一棵 n 个点的树，如果其中 k 个点标记为关键点（关键点的集合记作 S），则有：^\text{CodeForces-1790F}
\min_{u,v\in S,u\neq v}\{{\rm dis}(u,v)\}\leqslant \frac n k
其中 {\rm dis}(u,v) 是 u,v 两点间简单路径上的边数。
【语言基础】/【C++ 标准库】/【STL 容器】/【关联式容器】

set/map中的每个节点（元素）包含值、左右指针、颜色标记等，因此空间常数是较高的。（据 DeepSeek 所说，在set<int>中存储单个元素需要至少 32 个字节，实际占用可能更多）

因此，在题目卡空间的时候，请谨慎使用set/map和其他较复杂的 STL 容器。
【数据结构】/【链表】

有这样一个问题：给定 n 的排列 p，要求对于每个 i 求出 p_1 ~ p_{i-1} 中小于 p_i 的最大元素（或报告不存在）。

看到这个问题，很多人的第一反应是使用平衡树、权值线段树等维护当前前缀的所有元素。但实际上，有一个好写常数小的 {\rm O}(n) 做法：^\text{洛谷-P4696}

如果我们倒着求解，那么操作就剩下求一个元素的前驱、删除元素两种——于是用链表即可。

这启示我们：由于链表无法二分，所以在指定位置插入元素是困难的（这种情况下只能用平衡树、权值线段树等）；但删除指定的元素是容易的。

2025-08-13

【图论】/【树上问题】/【树上启发式合并】

启发式合并的思想不仅仅可以用于集合合并。例如，在一些树上递归统计类的问题中（树大小为 n），如果对于每个子树计算答案的复杂度都和其中一个子树（二选一均可推出答案）的大小成线性，那么选择较小的那个子树，总的时间复杂度就降到了与启发式合并相同的 {\rm O}(n\log n)。^\text{洛谷-P7118}

2025-08-12

【数学】/【数论】/【分解质因数】

遇到与“几个数的质因数的并集”（即几个数的乘积的质因数）有关的问题时，由于质数表很大，所以直接维护质因数并集是比较困难的。但是，有以下几个有用的结论：
- 一个数 n 的质因数个数只有 {\rm O}(\log n) 个。
- 一个数 n 至多只有一个超过 \sqrt{n} 的质因数。^\text{洛谷-P2150}
【算法基础】/【贪心】

在“确定最佳顺序”的贪心问题中，一般的做法都是将所有元素按某种关系排序后再贪心从前往后选择。

邻项交换 是一种实用的发现贪心策略和证明其正确性的方法。如果将两个满足特定关系元素顺序调换后答案一定不会变得更劣，并且这种特定关系可以被排序，那么按这种关系排序后贪心选择通常是最优的。^\text{CodeForces-1601D}

2025-08-11

【专题】/【偏序与数点】

一些看似是高维偏序统计的问题，如果题目的特殊性质使得对于任意两个元素 a(x_1,x_2,\dots,x_n),b(y_1,y_2,\dots,y_n)，若 x_1>y_1，则必然存在 i\neq 1 使 x_i>y_i，那么完全可以将第一维省去，从而降维降低复杂度。
【动态规划】/【树形 DP】/【换根 DP】

适合使用换根 DP 解决的问题：
- 没有指定固定的“根节点”和“子树”；
- 需要对于每个节点求解该节点为根时 / 仅该节点在某些限制下时整棵树的信息并。
- 在已知子树信息并的情况下，子树对父节点的贡献可以快速加入和撤销。

2025-08-09

【图论】/【树上问题】

在处理与“基环树上路径”有关的路径路径最优值查询问题时，可以删去环上的一条边 (u,v)，然后对于每个询问 (s\rightarrow t) 依次讨论 s\rightarrow t、s\rightarrow u\rightarrow v\rightarrow t、s\rightarrow v\rightarrow u\rightarrow t 的几种情况。这样就把问题转化为了树上问题。^\text{洛谷-P4949}

2025-08-08

【数学】/【数论】/【最大公约数】

遇见一些同时含有 \gcd(a,b) 和 {\rm lcm}(a,b) 的等式时，可以设 d=\gcd(a,b)，将 a,\,b,\,{\rm lcm}(a,b) 分别表示为 dp,\,dq,\,dpq（其中 p,q 互质），从而简化式子。^\text{CodeForces-1499D}
【算法基础】/【倍增】

倍增算法通常用来解决下面一类问题：

给定一个初始元素，要求对该元素进行 k 次相同的操作（或不断操作直到满足某一条件），求操作完的元素或所有操作的信息并。

当操作次数很大时，就可以使用倍增算法将操作次数从 {\rm O}(k) 优化至 {\rm O}(\log k)。前提是：
- 初始元素通过若干次操作能够得到的元素数量不多（时空复杂度至少为元素数量乘上 \log k）；
- 若要不断操作直到满足某一条件，则要能够根据当前元素或操作次数快速判断当前状态是否满足条件。

（笔记：树上连通块“点-边=1”）\ 时间有限，之后再补（~~啊啊啊这笔记都晾在这里多久了~~）

2025-08-07

【其它】/【随机数据】

随机数据的一些常见性质：
- 树
- 节点数为 n，则最大深度为 {\rm O}(\log n)
- 序列
- 最长上升子序列长度为 {\rm O}(\sqrt{n})
【专题】/【括号序列】

所有 n 个节点的有根树都可以和所有长度为 2n-2 的合法括号序列一一对应。具体方法是 DFS 一边整棵树，若往下访问一个点的儿子则向序列中插入一个 (，若从一个节点回溯到其父亲则插入一个)。

任取得到的括号序列的一个子段，将其中的所有匹配括号删去，得到的序列)))...)(...(((一定对应树上的一条简单路径。并且，树上的任意一条简单路径也都能对应括号序列的子段（但可能可以对应不止一个）。这条结论是树上莫队的基础。

2025-08-06

【图论】/【树上问题】/【树的直径】

定义一条树上简单路径的长度为这条路径上的边数。\ 若树的直径长度是偶数，则所有直径的中点一定为同一点。\ 若树的直径长度是奇数，则所有直径的最中间那条边一定为同一条边。\ （自证不难 \"{\smallsmile}）
【图论】/【树上问题】/【树的中心】

如果节点 x 作为根节点时，从 x 出发的最长链最短，那么称 x 为这棵树的中心。

可以证明，若树的直径长度（边数）为偶数，则树的唯一中心在树直径的中点上。如果树直径长度为奇数，则树有且仅有两个中心，位于树的直径最中间那条边的两端。
【字符串】/【前缀函数与 KMP 算法】

变种字符串匹配类问题能够使用 KMP 求解的条件：
1. 若两个字符串被认为是相等的，则两者长度相同（记为 n），且对于任意 1\leqslant l\leqslant r\leqslant n，两者的子段 [l,r] 也被认为是相等的。
2. 若 a,b 相等，b,c 相等，则 a,c 也相等（即：相等关系满足传递性）。
【数学】/【组合数学】/【卡特兰数】\ 【图论】/【树上问题】

约定：两棵有根树是不同的，当且仅当满足下列条件之一：
- 两棵树的根节点的子节点数目不相等；
- 设两棵树根节点子节点数量为 a，存在至少一个 i\in [1,a] 满足两棵树的根节点从左至右第 i 个子节点为根的子树是不同的。（也就是说，区分子树的先后顺序）
第 n 项卡特兰数是：
- 有 n+1 个节点的不同的有根树数量。\ 理解：所有 n+1 个节点（n 条边）的不同的有根树都能与所有长为 2n 的括号序列一一对应。
- 有 n 个节点的不同的有根二叉树数量。\ 理解：不好感性理解……把 n 个节点二叉树数量的递推式推出来，就会发现和卡特兰数递推式是一样的。

2025-08-05

【其它】

一些最优化问题要求选择若干元素（每个元素有两个属性，也可以有更多，不过会更难处理），要求最小化选择的元素的第一属性的最大值和第二属性的最大值之和。（最大化最小值同理。）

显然，这个问题是没法二分答案做的。遇到这类问题，首先应该考虑枚举第一个属性的最大值，再在这个前提下最小化第二属性的最大值（如果复杂度太高，应重点优化最小化第二属性的部分）。
【其它】

在一些求“贡献小于/小于等于定值 k 的方案数”问题中，如果“贡献小于 k 的方案数”不好求但“贡献等于 k 的方案数”较好求，且每个贡献小于 k 的方案都能对应一个不同的、贡献大于 k 的方案，那么可以采用 \ （总方案数 - 等于 k 的方案数）/2 \ 来求小于 k 的方案数。^{\text{ CodeForces-1227F2}}\;^\text{DMYOJ-1868}
【语言基础】/【C++ 标准库】/【bitset】

使用 bitset 优化算法常数时，建议将优化的常数算进复杂度中（即：将优化前的复杂度除以 \omega）。因为 bitset 对常数的优化很大，优化后甚至可以使 {\rm O}(n^3) 的算法跑过 n=1000。

2025-08-04

【数学】/【组合数学】

重要的定理：二项式定理
(a+b)^n=\sum_{i=0}^n \binom{n}{i} a^i b^{n-i}
二项式定理最主要的用途是用来简化形如 \sum C_n^i v^i 的式子。^\text{DMYOJ-3256}

更确切的说，只要看到形如 a_0C_n^0+a_1C_n^1+a_2C_n^2+\dots+a_nC_n^n 的式子（也就是说，将杨辉三角某一行的全部元素配系数后求和），就要考虑用二项式定理了。
【数学】

等比数列求和公式：
\sum_{i=0}^n p^i=\frac{p^{n+1}-1}{p-1}
注意：p 不能为 1。（如果为 1 则答案就是 n+1）

2025-08-03

【数学】/【组合数学】

如果要求杨辉三角一横行上的一段元素和（允许离线），那么莫队是最简单的做法。不难发现，如果使用莫队维护 (C_i^0+\dots+C_i^j)，那么它是可以在 \text{O}(1) 的时间复杂度内转移到\
$(C_i^0+\dots+C_i^{j-1})$\ $(C_i^0+\dots+C_{i-1}^{j})$\ $(C_i^0+\dots+C_{i+1}^{j})$ 的。（后两种可以根据$C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$ 得到）。 - 结合之前介绍的求杨辉三角一列上元素和的方法（2025-07-30 第 1 条），我们不仅能求杨辉三角上任意方向上一段元素的和（前提是能离线，能接受 $O(\sqrt{n})$ 的莫队），甚至还能求出任意一个三角形的元素和（自己想想吧！）

2025-08-01

【数据结构】/【线段树】\ 【数据结构】/【二叉搜索树 & 平衡树】

如果要维护一个有序序列，实现快速插入、删除、求指定位置值、二分，且序列内的值范围不大，那么使用权值线段树和普通平衡树（set）都是可以的。在这类问题中，如果在一些情形下无法使用 set（例如：求一个元素的 rank），那么我觉得比起手写平衡树，应该使用权值线段树会更好一些（因为后者自己更熟悉）。

2025-07-31

【动态规划】/【动态规划基础】

有这样一类问题：给定一个序列，要求选择序列中的一些（不要求连续的）元素，使这些元素（通过某些方式计算出来的）贡献最优。

解决这类问题的序列 DP 有 2 种常见状态设计方法：
二者优缺点的比较：
- 由于不要求连续，第一种方法单个状态的转移数量常常是 \text{O}(n) 的。相比之下，第二种方法的单个状态囊括了一个状态之前所有可以转移到此的状态，单次转移的复杂度更优。（例如：最长公共子序列问题，采用第二种方法的复杂度明显比采用第一种方法（枚举公共子序列的上一位对应位置）复杂度更优）
- 第二种方法的状态不再与最后一个选择的位置相关，所以可能需要在状态中多记录一些第一种方法中与最后选择位置有关的附带属性。并且，如果计算贡献的方式与选择的相邻元素对有关（例如：玩具装箱问题（斜率优化板子），贡献的计算与选择的两个相邻区间末尾位置的前缀和之差的平方有关），那么第二种方法就不是很好做了。
在解决这种问题的时候，建议优先考虑第一种方法（因为解决范围较广），如果复杂度过高再往第二种方法考虑。

2025-07-30

【数学】/【组合数学】

有用的公式：\displaystyle\sum_{i=k}^nC_i^k=C_{n+1}^{k+1}（可用归纳法证明）

结合前缀和思想，这个公式可以用来快速求杨辉三角上任意一列上任意一段的元素和。
- 补充笔记：2025-08-03 第 1 条

2025-07-29

【计算几何】/【扫描线】

例题：给定数轴上 n 个区间 [a_i,b_i]，记这些区间的集合为 S。有 q 组询问，每次询问区间 [x_i,y_i] 是 S 中多少区间的子区间。n,q\leqslant 10^5。

这类问题中，S 中给定的每个元素能为数轴上的若干左、右端点在一段定区间内的区间产生一定的贡献，要求我们统计任意区间的贡献（支持离线）。解决这类问题有一种常用技巧：如果我们建立一个平面直角坐标系，以左端点为横坐标，右端点为纵坐标，那么所有的区间都被转化为平面上的点，而 S 中元素能贡献的区间范围则能被表示为平面上的矩形。于是，做完这种转化之后，我们只需要离散化后扫描线求解每个待求贡献的点被覆盖的次数即可。

2025-07-28

【数据结构】/【线段树】

两个简单函数的合并（即：已知两个函数 f(x) 和 g(x)的图像，求 f(g(x)) 的图像）是满足结合律的。这使得“单点修改函数、求区间函数合并值”的问题可以使用线段树求解。^\text{DMYOJ-3246}（好像去年 CSP 集训的时候我们就做过一道类似的题）
- 与函数合并类似，矩阵乘法等一些其他满足结合律的运算也可以放进线段树，从而实现带修改的区间查询。

2025-07-27

【动态规划】

在一些 DP 问题中，如果状态数组的取值是“是否合法”（0/1），我们可以尝试将原问题转化为最优化问题，从而简化状态，以降低复杂度。更具体一点说，可以尝试将同类状态分组合并，如果每组中存在可以转移到 [这组所有状态可转移到的状态] 的状态，我们可以只保留这个状态（将其作为这个组的新状态的最优化属性）。^\text{DMYOJ-3245} ^\text{AtCoder-arc157\_e}

2025-07-26

【其他】

数轴上的两个区间 [L_1,R_1] 和 [L_2,R_2]（(L_1<L_2) 或 (L_1=L_2,R_1\geqslant R_2)）只有三种关系：不交（R_1<L_2）、包含（R_2\leqslant R_1）、一般相交（L_2\leqslant R_1<R_2）。由此可推得，对于一个区间的集合，如果将所有区间按（(L_1<L_2) 或 (L_1=L_2,R_1\geqslant R_2)）的顺序排序，则：
- 如果一个区间的集合中所有的区间均两两不包含，则一定有 L_i<L_{i+1},\;R_i<R_{i+1}。^\text{DMYOJ-3242}
【字符串】

将字符串 S_{[1,n]} 的长度为 p 的前缀和长度为 n-p 的后缀调换顺序，与将 S 循环左移 p 位是等价的。（最终得到的都是 S_{p+1},\dots,S_n,S_1,\dots,S_p）。
- 在解决相关问题时，要熟练学会将其中一种操作转化为另一种更好处理的操作。
【字符串】/【前缀函数与 KMP 算法】

KMP 的 {\rm O}(n) 复杂度是基于均摊的（每次跳前缀是单向的，类似于 SA 求 height 数组的过程）。因此，在^\text{CodeForces-1721E}这类问题中，要在一个字符串的后面接上不同的后缀，并求接完后每个字符串的前缀数组，如果我们对每个后缀都用固定前缀的前缀数组跑一遍 KMP，那么复杂度和后缀总长度 不是成线性的。如果前缀长为 n，一个后缀长度为 a_i ，后缀数量为 k，那么复杂度最坏情况可达到{\rm O}(\sum(n+a_i)) 也就是 {\rm O}(kn+\sum a_i)。

类似地，我们可以推知：如果问题是在固定前缀、不同后缀的文本串上匹配模式串的话，那么最坏时间复杂度为单个后缀 {\rm O}(m+a_i)，其中 m 是模式串长度，a_i 是后缀长度。

如果这样的复杂度无法接受，应该考虑使用 KMP 自动机（也就是只有 1 个模式串的 AC 自动机），将复杂度由均摊的 {\rm O}(n) 转化为严格的 {\rm O}(nw)。（w 是字符集大小）
- 但是：^\text{洛谷-P4824}这题中直接 KMP 又是可以的（推一下你会发现，复杂度能接受）。所以，在遇到上述情况的时候，能否直接使用 KMP 还得具体情况具体分析，不可一概而论。
【字符串】/【字符串哈希】\ 【数学】/【高精度计算】

在一些要给大数做四则运算，看似要使用高精度的时候，如果我们不需要知道精确的运算结果，只需要判断它和另一个大数是否相等，那么我们将这些大数哈希（其实也就是取模）后比较总是比高精度计算更加高效。（但哈希进制必须取 10 才能直接进行运算）^\text{CodeForces-898F}
【数据结构】/【单调栈】

处理与“静态区间最大、最小值的位置”有关的询问，最常用的做法是将所有的区间按右端点排序，然后就可以用单调栈维护固定右端点时左端点最值的位置了。^\text{CodeForces-1849E}
- 老师说另一种常用做法是笛卡尔树……但我还没研究过。

2025-07-25

【图论】/【最短路问题】/【最短路】

最短路问题有很多变种，例如求“点 s 到一个点u 的单源最短路被更新后需和特定值取 max/min”^\text{DMYOJ-3241}。只要这些问题仍然满足以下两大特性：
1. 若 s\rightarrow u 的答案变得更优，则s\rightarrow u\rightarrow t 的答案一定不会变得更劣；
2. 用点 u 更新点 v 的答案，更新后点 v 的答案一定不会比原来点 u 的答案更优。（对应传统最短路问题“没有负边权”）
那么就可以用 Dijkstra 算法求解。

2025-07-23

【数据结构】/【线段树】

线段树是专门为“修改+区间查询”的序列问题设计的数据结构。因此只要查询的信息并允许快速合并，就要首想线段树！（当然如果能用树状数组等常数更小的数据结构更好）
- 例如：线段树常用来维护“动态区间内贡献最大的 k 元子序列（k 是很小的常数，如 2,3）”^\text{洛谷-P7706}
【专题】/【懒标记】

打懒标记是一种经典常用的快速处理区间修改的思想。^\text{CodeForces-1638E}
- 补充笔记：2025-09-02 第 1 条
【其它】

在题目中遇到“求符合某条件的元素/集合/序列个数”，第一步应该是明确满足“某条件”的（更简单，能直接计算的）充要条件。
- 如：^\text{DMYOJ-3236}中，看到“求 b 数组能『碰瓷』的 a 的子数组个数”，首先应该想一个数组 T 能『碰瓷』另一个数组 S 的充要条件，然后再想如何快速维护和判断这些条件。

2025-07-22

【数据结构】/【单调栈】

单调栈就是维护每个元素前/后第一个比它大/小的元素的数据结构。在题面中看到上面加粗的字，要快速想到单调栈，它常常能很好地优化复杂度。^\text{DMYOJ-3235}
【其它】

对于长度为 n 的数组 A 和长度为 m 的数组 B，可以用 {\rm O}(nm) 的时间复杂度 DP 找到 A 中所有和 B 相等的子序列（信息并）。^\text{DMYOJ-3236}
【字符串】

一个可能会用到的结论：（字符串下标从 0 开始； A_i 表示字符串 A 下标 i 对应位置的字符；A_{[l,r)} 表示 A_l 到 A_{r-1} 这一段子串）

定义长度为 m 的字符串 T 是长度为 n 的字符串 S 的周期，当且仅当以下条件满足：
如：ab,abab,ababa均是ababa的周期，但a,abc,ababab均不是。

结论：对于长度为 n 的字符串 S，若 S_{[0,m_1)} 和 S_{[0,m_2)} 均是 S 的周期，且 \mathbf{m_1+m_2\leqslant n}，那么 S_{[0,\gcd(m_1,m_2))} 也是 S 的周期。

2025-07-21

【其它】

遇到与按位或有关的最优值问题，要想到从高往低按位处理。^\text{CodeChef-MINORPATH}
【算法基础】/【贪心】

一些贪心题的解法完全依赖一些通过尝试得到的（或者说：摸索、瞎搞搞出来的）套路，如果没有推出这些套路，那么题就完全无从下手。因此，在毫无头绪的情况下，要敢于去尝试发现隐藏的套路（但这么做通常考验思维的灵活性，有时会耗费很多时间）
- 比如，^{\text{CodeForces-1763C}}这题用常规思路（搜索、DP等）是没法做的。解决这题的关键在于发现对于任意序列操作的策略都是相同的，仅和最大值的位置有关系。
- 实际上，手动造一些样例推一推对发现这些套路是有帮助的。
【其它】

“黑白染色”的题目中，可以通过反转奇数格/偶数格颜色使“两个相同点之间的关系”转化为“两个不同点之间的关系”。后者往往比前者更好处理一些。^{\text{Gym-105484B}}
【其它】

交互题中，第一步应该想“如果查询次数没有限制应该怎么做”。

2025-07-11

【动态规划】/【DP 优化】/【四边形不等式优化】

有一点需要明确：如果要用 2025-07-08 第 1 条笔记所述的方法画图判断是否满足四边形不等式，那么在画出来的图像中，横轴代表待求的不同最大/最小值，每一支图像代表的是决策点。也就是说，图像反映的不是同一个待求值随不同决策点的取值变化情况，而是同一个决策点转移到不同待求值时的每个待求值的取值。千万不要把二者搞混了！^\text{AtCoder-abc384\_g}
【动态规划】/【DP 优化】/【四边形不等式优化】

四边形不等式不仅可以优化区间分拆问题的 DP【f_i=\begin{matrix}\min\\\max\end{matrix}\{f_{j-1}+w_{j,i}\}】，还可以用于求解一些和区间分拆 DP 类似的非 DP 问题：
- 已知（或可以求出）数组 a 和 w，对于每个 i 求 ans_i=\begin{matrix}\min\\\max\end{matrix}\{a_{j}+w_{j,i}\}。{\rm O}(n^2) 的朴素算法无法通过。
- 虽然不是 DP ，但不同 i 的答案之间也可能存在决策单调性（只要 w 满足四边形不等式）。在优化这类问题的时候可以往这方面想想。
【杂项】/【离线算法】/【莫队算法】/【普通莫队算法】

使用普通莫队算法维护区间信息并需要两个条件：
1. 支持离线
2. 支持快速插入和删除元素
【图论】/【网络流】/【最大流】\ 【图论】/【网络流】/【费用流】

一些与“点的经过次数”有关的最大流/费用流建模套路总结：
- 经过一个点的流量最多为 1（或最多为某个定值）
将该点拆成两个点（入点和出点），入点向出点连一条容量为 1 的边。原图中的其他边由对应起点的出点连向对应终点的入点。
- 最大费用流问题中，若一个点的流量超过 1，其费用（正的）只计算 1 次
同样将该点拆成两个点，中间连两条边，一条容量为 1，费用为原题中流过该点的费用；另一条容量为经过该店最大流量减 1。（若没有最大流量限制则设为无穷大）

2025-07-10

【动态规划】/【DP 优化】/【四边形不等式优化】

一个满足四边形不等式的 w(j,i) 在经过取整、与常数取 max/min 等操作之后一般不再满足四边形不等式。（这是因为这些操作一般会让图像上函数的斜率产生较大变化）
- 所以，如果题目求结果取整或取 max/min 后的值，一定不要想当然，直接在二分队列求解时取整或取 max/min（即使这么做的结果是开 double 甚至 long double），而是应该在输出时再操作！^\text{洛谷-P1912}^\text{洛谷-P3515}

2025-07-09

【动态规划】\ 【算法基础】/【贪心】

思考一道题如何贪心，一般都是从思考如何 DP 开始的。（但也会有例外——见 2025-07-21 笔记 2）正因如此，在遇到 DP 无法直接优化的时候，我们要敢于大胆猜结论（有时间的话就进一步证明一下），从而推出可能的贪心做法（或是重新设计状态优化 DP）。
- 例题：给出一个 n 个点的树和正整数 k，要求从树上选出若干长度为 k 的链（长度指链上点的个数，含端点），使任意两条链均没有公共点。问最多能选出多少这样的链。1\leqslant k\leqslant n\leqslant 10^6。^\text{CodeForces-1039D}^\text{（弱化版）}
- 如果直接使用 DP，可以设计状态 f_{u,i} 表示在 [ 存在一条从 u 向下，长度 ( 至少 ) 为 i 且所有点均没有被选的链 ] 的前提下 u 的子树内最多可选出链的条数。（转移方程自己想）但这么做时间复杂度为 {\rm O}(nk)，无法通过，且不好直接优化。
- 但我们可以通过猜测发现一个结论：对于一个节点 u，如果在 u 的每个子树中选完若干条链之后，仍然存在一条没有被选、经过 u 点、符合要求的链，那么选这条链（和先不选这条链，把上面没选的节点保留，到u 的某个祖先时再选相比）一定是不劣的。于是我们只需维护每个子树从根向下最长的所有点均未被选的链的长度，就可以得到一个 {\rm O}(n) 的贪心做法。
- 补充笔记：2025-07-21 第 2 条
【其它】/【卡常】

基于递归实现的树上 DFS 常数是相对较大的。尤其是在需要多次执行同一个 DFS 的时候，递归做法常常比非递归做法更慢。所以，在树形 DP 等需要树上 DFS 的问题中，可以预先处理出树上节点的 DFS 序，然后将节点按 DFS 序搬到序列上，倒序求解。这样可以一定程度上降低常数。
- 当然，正式比赛中通常不会出现常数问题。

2025-07-08

【动态规划】/【DP 优化】/【四边形不等式优化】\ 如何理解胖头鱼所说的“决策单调性本质上是凸性”这句话？对此我进行了思考，得到了下面这些发现。

把四边形不等式变形一下，可以得到
w(b,d)-w(b,c)\leqslant w(a,d)-w(a,c)\qquad①
于是，对于一个转移方程形如 \displaystyle f_i=\min_{j\leqslant i}\{a_j+w(j,i)\} 的DP 问题（此处 a_j 也可以是 f_{j-1} 等，但必须是定值），我们不妨对于每个 j 画出 a_j+w(j,i) 随 i 变化的函数图像（其中，如果j_0是某个定值，我们将 a_{j_0}+w(j_0,i) 随 i 变化的图像，也就是所有i\geqslant j的点 (i,a_{j_0}+w(j_0,i)) 称作图像 j_0）。\ 不难发现：
$\forall j_1\leqslant j_2\leqslant i$，图像$j_2$ 在 $x=i$ 时的斜率均**小于等于**图像$j_1$ 在 $x=i$ 时的斜率。类似地，如果转移方程是 $\displaystyle f_i=\max_{j\leqslant i}\{a_j+w(j,i)\}$且满足四边形不等式，也可以得到类似的结论：\ $\forall j_1\leqslant j_2\leqslant i$，图像$j_2$ 在 $x=i$ 时的斜率均**大于等于**图像$j_1$ 在 $x=i$ 时的斜率。 - 举个例子，[$^\text{洛谷-P3515}$](/problem/P3515)的其中一种情况的转移方程为$\displaystyle f_i=\max_{j\leqslant i}\{a_j+\sqrt{i-j}\}$，按照这道题的样例，可以画出这样的一张图。\ ![](https://cdn.luogu.com.cn/upload/image_hosting/noskc44d.png)\ 在所有的图像中其中任选两个不同的 $j_1<j_2$，$j_1$ 在某个点的斜率总是小于 $j_2$ 在此处的斜率。因此，这道题的 DP 具有决策单调性。那么这跟“凸性”又有什么关系？我是这么理解的。观察上图我们其实可以发现，如果每个 $j$ 画出的图像是**一样的**，且该图像是一个**凸函数**（若原问题求最小值则需要是下凸函数（如 $y=x^2$ 的图像）；如果求最大值则需要是上凸函数（如 $y=\sqrt{x}$ 的图像）），则该问题一定满足四边形不等式，具有决策单调性。（满足上面所说的斜率条件） - 但是，上面这一点是满足四边形不等式的一个**充分不必要条件**。也就是说，一个满足四边形不等式的 DP 问题，它画出来的图像不一定都是如上面所说的凸函数。[$^\text{洛谷-P4767}$](/problem/P4767) 总而言之，判断一个 DP 是否具有决策单调性（满足四边形不等式），我们也可以采用比较图像斜率的方法，而不需要总是直接去代四边形不等式。在某些转移方程比较复杂的时候[$^\text{洛谷-P4767}$](/problem/P4767)，前者通常会比后者更加方便。 ~~（哇，第一次写这么长）~~ * 补充笔记：2025-07-10 第一条 * 补充笔记：2025-07-11 第一条
【图论】/【网络流】/【最小割】\ 【图论】/【网络流】/【最大流】

一些最小割问题建模得到的网络点数或边数过多（且无法优化建图），不能使用常规的网络流算法解决。这种时候，如果图中边的容量是由题目的一些性质决定的（而不是直接由输入数据给出），我们就要尝试采用其他方法（例如 DP）求解最小割。^\text{AtCoder-abc332\_g}
- 尽管在常规办法中，我们总是用最大流算法解决最小割问题，但如果在最大流问题中遇到这种情况，我们不排除要将其转化为最小割问题。
【其它】

现在有这样一个问题：\ 有一个长为 n 的整数序列（初始为 0），可以通过操作使其中一个元素增加 1 或减少 1。要求维护序列的最大值（最小值）。

这个问题效率最高的做法异常简单，不需要堆，更不需要线段树/平衡树！

做法：新开一个数组维护序列中每个值的出现次数。若操作是增加 1，则直接用增加后的值更新最大值；否则，判断一下当前的数是不是数组中唯一的最大值，如果是，则将最大值减去 1。时间、空间复杂度均为\text{O}(n)。^\text{洛谷-P1997}

2025-07-07

【其它】\ 【杂项】/【离线算法】/【莫队算法】/【普通莫队算法】\ 大部分情况下，离线做法的思维和实现难度都不会比在线做法更难。

遇到询问区间信息并的问题，如果问题可离线、可快速添加和删除元素，要迅速地想到莫队。

2025-07-05

【其它】\ DP 转移方程中的绝对值通常不好处理，所以一般要按正负分类讨论。^\text{洛谷-P3515}
【动态规划】/【DP 优化】/【四边形不等式优化】\ 一个带有分母或根号的式子具有决策单调性，不代表它取整后也具有决策单调性。^\text{洛谷-P3515}

带有取整号的式子很少具有决策单调性。决策单调性本质上是凸性，你取整之后原来的凸函数就变成阶梯状了。\

2025-07-04

【图论】/【网络流】/【最小割】\ 一些常见最小割建模套路总结——\ （问题：有若干元素，选择每个元素可以获得一定收益 [ 其实也可以为 0 ]。一般来说，这个收益就是元素代表的点与源/汇点之间边的容量。以下讨论的所有“收益”和“代价”都是非负整数。）\ （注 '*' 的表示要求此关系构成的图是二分图）
- 同时选择某两个元素要付出代价 *
  
  把两个元素放在二分图的两边，中间连一条容量为代价的边即可。割掉这条边表示付出该代价。
- 若选择了几个元素中的至少一个，需要付出代价
把元素放在源点一边，代价单独建点放在汇点一边并向汇点连一条容量为代价的边，然后将每个代价的点从对应的元素各连一条容量为正无穷的边。（其实就是个最大权闭合子图问题）
- 同时选择某两个元素可获得额外收益 *\ （这个关系一般和前两个关系中的一个或两个同时存在，毕竟一个问题里总是得有代价的。如果是和第一个关系同时存在的话，则要求这两个元素必须在二分图同一侧。）
假设该关系对应的两个元素都在源点一侧。那么单独建一个点，从源点向该点连一条容量为额外收益的边，再从该点向两个元素的点各连一条容量为正无穷的边即可。\ 汇点一侧同理。\ 见下图：（其中 X,Y 是元素，A,B 是新建的点，假设额外收益为 1）

2025-07-03

【其它】\ 一般来讲，有序数组都比无序数组更好处理，所以归并排序中的“归并”思想（在 \text{O}(n) 内实现两个数组的合并）在一些与有序数组相关的场合下非常实用。
- 例如，如果要批量修改（对一段连续区间的修改不改变区间内元素的大小顺序）有序数组 a 里的某些元素，最快的做法是（\text{O}(n)）：
  1. 将 a 中要修改的元素放到新数组 b 中，不修改的元素放到新数组 c 中（均不改变原本的顺序）；
  2. 批量修改 b 中的元素（可以打标记）；
  3. 归并 c 和修改后的 b 得到新的 a。

2025-07-02

【杂项】/【离线算法】/【CDQ 分治】\ （这里以三维偏序问题为例）在 CDQ 分治的排序过程中（无论是开始之前按 "x-y-z" 排还是计算贡献时按 "y-z" 排），如果遇到关键字相等的插入操作和查询操作，一定要把查询放在后面！（我吃过好几次这个亏了，必须得写进来）
【语言基础】/【C++ 标准库】/【bitset】\ 下面这种方式可以给一个 bitset 初始化或整体赋值。
```
bitset<N>bs;
bs=0;
//重载"=": 将 bitset 设为后面整数的二进制形式（在这里就是设为全0）
```
然而，容易被忽视的是，这么做是 \text{O}(\frac{n}{\omega}) 的。因此在一些情形下不能使用。因此，还是尽量避免使用这种方式为妙。
【图论】/【2-SAT】在 2-SAT 问题的建图中，我们只关心“从一个点能不能到达另一个点”，而不关心图的具体结构（比如这两个点中间经过了几条边、哪些点）。所以，我们可以通过加入辅助点来对图进行简化，减少边的数量，从而降低复杂度。
- 例如：在^\text{洛谷-P6378}这题中，一个点的「选」状态需要向组内其他所有点的「不选」状态连边，这么做会让边的数量达到 \text{O}(n^2)。于是，我们可以像下图一样各设一条向左、向右的链，让链上的每个节点到达该点之前（之后）的每一个对应点「不选」状态，然后让「选」状态的边直接连到链上即可。\ \ 上图中，1,3,5,7 对应原图的「选」状态，2,4,6,8 对应「不选」状态。
【图论】/【树上问题】/【树的直径】\ 定理：向一棵树（有边权）上加入一个点，得到的新树的直径最多会改变一个端点，长度最多增加 1 。（证明：见 OI-Wiki 树的直径章节定理 1 的证明）\ 定理：将两棵树用一条边连接得到一棵新树，则新树的的直径的两个端点在一定都是连接前的两棵树的直径的端点。（来自代码源课程，证明尚不清楚）

2025-07-01

【动态规划】/【DP 优化】/【斜率优化】\ 斜率优化题的转移方程不一定总是形如 f_i=\begin{matrix}{\min}\\{\max}\end{matrix}\{p_ia_j+b_j\}，也有可能是 f_i=\begin{matrix}{\min}\\{\max}\end{matrix}\{p_ia_j+q_ib_j\}。很显然，只要将定值 q_i 提出来变成 \{q_i(\frac{p_i}{q_i}a_j+b_j)\} 就转化为了常规的情况。^\text{洛谷-P4027}
【图论】/【网络流】/【最大流】/【Dinic 算法】\ 如果需要令 Dinic 算法的实际运行时间接近其理论上界，我们需要构造有特殊性质的网络作为输入。由于在算法竞赛实践中，对于网络流知识相关的考察常侧重于将原问题建模为网络流问题的技巧。此时，我们的建模通常不包含令 Dinic 算法执行缓慢的特殊性质；恰恰相反，Dinic 算法在大部分图上效率非常优秀。因此，网络流问题的数据范围通常较大，“将 |V|, |E| 的值代入 \text{O}(|V|^2|E|) 以估计运行时间”这一方式并不适用。实际上，进行准确的估计需要选手对 Dinic 算法的实际效率有一定的经验，读者可以多加练习。\
_如果你确定一道题用网络流，你就只管用就行了。_\ $\hspace{10cm}$——胖头鱼 - 在[$^\text{洛谷-P4174}$](/problem/P4174)这一题中，Dinic 算法在一个点数约为$5\times10^4$，有向边数约为 $2\times10^5$ 的二分图上跑到了 100ms 以内。

2025-06-30

【图论】/【最小环】\ Floyd 算法的特性使得它可以在 \text{O}(n^3) 的时间复杂度内求解图的边权和最小环问题（不能处理负环）。在稠密图上，这种方法较优。^\text{洛谷-P4049}
- 如果题目要求的最小环必须是三元及以上的环，那么做法是：在第 k 轮最短路循环开始前，枚举与点 k 相邻的点 u,v (u,v<k)，用 dis_{u,v}+w_{u,k}+w_{v,k} 更新答案即可。
- 如果题目要求的环允许有二元环，那么只需初始时丢与每个 i 将 dis_{i,i} 初始化为 +\infty，在循环 (k,i,j) 的过程中允许 i,j 相等，最后用每个 dis_{i,i} 更新答案即可。^\text{【需要验证】}
【计算几何】/【凸包】\ 一条有用的性质：^\text{洛谷-P4049}\ 点 B 在凸多边形 A_0A_1A_2\dots A_{n-1} 内（逆时针顺序）\
$\forall i\in[0,n),\;\overrightarrow{A_i A_{(i+1)\bmod n}}\times\overrightarrow{A_i B}>0.

2025-06-28

【杂项】/【离线算法】/【CDQ 分治】\ 下面这种情形下的 DP 一般可以使用 CDQ 分治优化：
- 可以快速（比单独处理每个转移快）处理拓扑序连续的一整段状态 A 对另一整段状态 B（两段不交）的贡献。（例如：用扫描线处理二维偏序^\text{洛谷-P2487}；用斜率优化维护 A 的凸壳，将 B 中的状态在凸壳上二分^\text{洛谷-P4655}）
【动态规划】/【DP 优化】/【斜率优化】\ 【杂项】/【离线算法】/【CDQ 分治】\ 一般来讲，斜率优化的题目中，如果加入的决策点的横坐标和直线斜率均不单调，那么可以使用以下两种方法处理：^\text{洛谷-P4655}
1. CDQ 分治：参见 OI-Wiki 和上一条笔记。
2. 平衡树：用平衡树实现点的插入、删除和二分。思路简单，但 OI-Wiki 认为这种方法“实现繁琐”。
【数据结构】/【二叉搜索树 & 平衡树】\ 对比一下几种维护序列的数据结构，你会对平衡树产生一些新的认识：
- 数组：支持二分；不支持在任意位置快速插入和删除（\text O(n)）。
- 链表：支持快速插入和删除（\text O(1)）；不支持二分。
- 平衡树（不要求值有序的FHQ-Treap）：实际上可以看作是前两者结合后复杂度均摊的产物——既支持二分，又能够在\text O(\log n)的时间内实现在任意位置插入和删除。这一点和树状数组（常规数组、前缀和数组结合的产物）有点类似。
【数学】/【数论】/【筛法】\ 假设 [R-len+1,R] 是任意一段连续正整数，那么只要知道 [1,\sqrt{R}] 中的全部质数（可以用线性筛筛出），埃氏筛法就能够筛出 [R-len+1,R] 中的质数。总的时间复杂度为 \text{O}(\sqrt{R}+len\log\log len)。^\text{AtCoder-ABC412\_e}

线性筛不能做到这一点。

2025-06-27

【语言基础】/【C++ 标准库】/【STL 容器】/【无序关联式容器】\ unordered_map 等无序关联式容器容易被卡，所以只要能用其他的方式存储元素就不要用unordered_map！^\text{LibreOJ-121}
- 如果时间复杂度充裕，可以使用不易被卡的map替代unordered_map。
【图论】/【网络流】/【最小割】\ 使用最小割解决“选择元素使贡献最大化”的问题时，建模的套路一般都是固定的——

先假设所有贡献为正的元素都取了，所有为负的都没取，把所有的贡献都加上；然后设法将其中不合法的情况建模转化为“源点和汇点连通”，把【放弃不合法情况中元素所损失的贡献】作为连通源汇点的边的容量；最后再在得到的图上跑最小割，最小割的意义就是【通过放弃一些元素是情况变为合法所需要损失的最小贡献】，所以用贡献的总量减去最小割就能得到答案。
- 这种说法还是不够具体……要看几道例题才能明白。^\text{LibreOJ-6007}^\text{LibreOJ-6001}^\text{洛谷-P1646}
- 补充笔记：2025-07-05 第 1 条

2025-06-26

【杂项】/【离线算法】/【CDQ 分治】\ CDQ 分治可以用来优化一些在线问题（例如涉及三维偏序的 DP^\text{洛谷-P2487}）。但是在这种问题中，必须保证每个状态自己先被其他状态更新完后，才能去更新其他的状态。因此，CDQ 分治必须严格按照【递归处理左边\rightarrow左边更新右边\rightarrow递归处理右边】的顺序实现。（可以试试自行证明这样实现是合法的）
- 补充笔记：2025-06-28 第 1 条
【图论】/【有向无环图】\ 在一张 DAG 中，对于任意点 u：\ 经过点 u 的路径数量\,=\,以点 u 结尾的路径数量\,\times\,以点 u 开头的路径数量\ 这里的“路径”包含仅由一个点组成的路径。
- 所以，要想在一个 DAG 中求经过一个点的路径数量，可以 DP 两次求出以这个点开头、结尾的路径数量，再将结果相乘。^\text{洛谷-P2487}
【图论】/【网络流】/【最小割】\ 如果要求最小割割边的方案，正确的做法是：
1. 标记从源点出发经过残量网络上的有向边能够到达的所有点。这些点的集合就是割完后两个连通块的其中一个，记作 S。
2. 遍历一遍所有的边 (u,v)，若其满足 u\in S,v\notin S，则这条边会被割掉。
- 注意，流满的边不一定会被割掉！^\text{洛谷-P2762}
【语言基础】\ 不同系统的输入文件中，换行符可能不同（例如 linux 为\n，windows 为\r\n），因此在一些需要逐个读入字符的情况下，如果默认用\n指换行符，在某些评测系统里可能会出问题。所以，需要尽量避免使用ch==\n判断字符ch是不是换行符。^\text{洛谷-P2762}
- 替代方案——排除法：例如，如果输入数据里只有非负整数和分隔符（空格和换行符），可以用(ch!=' '&&!(ch>='0'&&ch<='9'))来判断字符ch是不是换行符。
- 当然，正式比赛中统一采用 linux 评测，应该是不会出现这种问题的。

2025-06-25

【图论】/【环计数问题】\ 如果将一个无向图（n 个点，m 条边，无重边，无自环）中的所有点按度数从小到大排序，并让所有的无向边从靠前的点指向靠后的点，那么所有点的出边条数均只有 {\rm O}(\sqrt m)。（自证不难）^\text{洛谷-P1989}
- 这条性质可以用于快速统计三元环、四元环等图形的个数。这种图形应该要满足以下性质：如果将所有点排成一条直线，那么这种图形在排成直线后的形状是固定的（只有一种或常数种）。

2025-06-23

【数学】/【概率论】\ 当随机变量 x 的取值为非负整数时：
其中 $n$ 是 $x$ 的最大取值。 - 这种优化一般用于不易直接求 $E(x)$ 但较容易求 $P(x>i)$ 的情况。[$^\text{AtCoder-ABC352\_g}$](https://vjudge.net/problem/AtCoder-ABC352_g)
【其它】\ 有这样一类问题：给定一个 n\times m 个方格的“棋盘”，要求在棋盘中取数或填数，棋盘中任意相邻（有公共边）的两个格子之间有一定限制（如：不能同时取；相邻两个数的和必须为给定的值）。\ 在这类问题中，通常可以想想将“棋盘”黑白染色。这样，相邻的两个格子颜色一定不同，于是我们就可以将这两种格子分开处理。^\text{洛谷-P2774}

2025年春季

2025-06-05

【数学】/【概率论】\ 求一个和式的平方的期望时，可以将其做如下转化：^{\text{Codeforces-1187F}}\ E\left(\left(\sum_{i=1}^n x_i\right)^2\right)=E\left(\sum_{i=1}^n\sum_{j=1}^n x_i x_j\right)=\sum_{i=1}^n\sum_{j=1}^nE(x_i x_j)

2025-05-28

【数学】/【数论】/【莫比乌斯反演】\ 遇到形如 \sum\limits_{d=1}^n f(d)\sum\limits_{t=1}^{\lfloor\frac n d\rfloor}g(t)\left\lfloor\dfrac n {dt}\right\rfloor 的式子（以下称“原式”）无法快速计算时，\ （尽管借助数论分块可以实现 \text{O}(n) 计算上述式子，但在某些多组数据的题目中仍然不够快^\text{洛谷-P3704}）\ 可以拆贡献，按 dt 分情况讨论：\
若 $f*g$ 是积性函数，那么就可以用线性筛 $\text{O}(n)$ 预处理出来。否则也可以 $\text{O}(n\log n)$ 手动狄利克雷卷积。无论如何，单次查询的复杂度就降到了 $\text{O}(\sqrt n)$。 - 如果将原式换成 $\prod\limits_{d=1}^n f(d)^{\small\sum\limits_{t=1}^{\lfloor\frac n d\rfloor}g(t)\left\lfloor\dfrac n {dt}\right\rfloor}$，也可以用类似的方法解决。[$^\text{洛谷-P3704}$](/problem/P3704) - 原式这种情况通常产生于 2025-05-27 第二条笔记中提到的分类讨论。这种情况下可以使用以上方法进一步化简式子。

2025-05-27

【数学】/【数论】/【数论基础】\ 一个数 n 的约数个数是 \text{O}(\sqrt n) 的。
【数学】/【数论】/【莫比乌斯反演】\ 当我们用莫比乌斯反演求含 \gcd(i,j) 的式子的值时，如果 \gcd(i,j) 出现在如 \sum\dfrac {ij}{\gcd(i,j)}、\prod\gcd(i,j) 等难以直接处理的位置时，一般会先拆贡献，按 \gcd(i,j) 分情况讨论。（否则能直接处理就直接处理）
- 例1：\sum\limits_{i=1}^n\sum\limits_{j=1}^m\dfrac{ij}{\gcd(i,j)}=\sum\limits_{d=1}^{n}d\sum\limits_{i=1}^{\lfloor\frac n d\rfloor}\sum\limits_{j=1}^{\lfloor\frac m d\rfloor}ij[\gcd(i,j)=1]^\text{洛谷-P1829}
- 例2：\
- 自然地，能直接处理的情况其实也可以按 \gcd 分类讨论解决，但最后通常会得到 \sum\limits_{d=1}^n f(d)\sum\limits_{t=1}^{\lfloor\frac n d\rfloor}g(t)\left\lfloor\dfrac n {dt}\right\rfloor 这样的式子。可以采用 2025-05-28 第一条笔记所述的方式进一步化简式子，使其与直接处理得到的结果一致。

2025-05-24

【数学】/【概率论】\ 在树上随机游走求期望经过次数问题中，可以用 \text{O}(n) 的时间复杂度递推求出每条边（往每个方向）的经过期望次数。^\text{CodeForces-1823F}

2025-05-23

【图论】/【连通性相关】/【强连通分量】\ Tarjan 算法的性质：如果将按 Tarjan 算法求出 SCC 的顺序给每个 SCC 编号，那么这个编号一定是缩点后每个 SCC 的反拓扑序（拓扑序反过来）。这条性质在 2-SAT 问题中有应用。（自证不难）
- 即使一次 dfs 没有覆盖所有点，这条性质也依然成立。因为对于第一次 dfs 没有覆盖到的点，我们总是可以把它们的拓扑序放在覆盖到的点的前面。

2025-05-19

【算法基础】/【分治】\ 【数据结构】/【ST 表】

和 2025-05-12 第二条笔记类似，在静态区间查询问题中，如果合并操作比插入操作复杂度更高，那么分治的复杂度可能会优于使用 ST 表。另外，如果问题是不可重复贡献的，那么分治的复杂度一般不劣于使用 ST 表。\ 以^\text{CodeForces-1100F}这题为例：
- 题目要求我们对每次查询维护某个子区间中所有元素的线性基。
- 做法 1：ST 表维护区间线性基。预处理 \text{O}(n\log n\log^2 V)，单次查询\text{O}(\log^2 V)。
- 做法 2：分治——将整个区间 [1,n] 划分为 [1,\frac n 2],[\frac n 2+1,n] 两部分，维护【 [\frac n 2,\frac n 2],[\frac n 2-1,\frac n 2],\dots,[1,\frac n 2]】和【[\frac n 2+1,\frac n 2+1],[\frac n 2+1,\frac n 2+2],\dots,[\frac n 2+1,n]】的线性基，再用相同的方法处理区间 [1,\frac n 2],[\frac n 2+1,n]。预处理 \text{O}(n\log n\log V)，单次查询\text{O}(\log n+\log^2 V)。

2025-05-12

【图论】/【图的存储】\ 当我们需要快速找到一条边的反向边的时候，适宜用链式前向星存边；其他时候一般适宜用 vector 邻接表。\ 具体来说，以下几种情况可能需要快速找反向边：
- 待遍历的图中有重边，不能使用x==fa判断一条边是否已走过。
- 网络流问题。
- 欧拉回路问题。
【图论】/【树上问题】/【树链剖分】\ 【数据结构】/【ST 表】\ 【图论】/【树上问题】/【树分治】/【点分治】\ 在处理静态、可合并、不可逆（没办法用前缀和）、可重复贡献（可使用 ST 表 \text{O}(1) 查询区间）的树上路径贡献查询问题时，如果将两段贡献合并的复杂度较高【高于 \text{O}(1)】，那么点分治在查询时的复杂度要略优于树剖（因为树剖合并次数是 \text{O}(\log n) 的，而点分治是 \text{O}(1) 的）。但由于常数原因，点分治不一定跑得更快）。\ 以^\text{洛谷-P3292}这题为例：
- 题目要求我们对每次查询维护树上两点路径上所有点点权的线性基。
- 做法 1：树剖+ST 表维护区间线性基（路径会被剖成 \text{O}(\log n) 条链，需合并 \text{O}(\log n) 次）。预处理 \text{O}(n\log n\log^2 V)，单次查询\text{O}(\log n\log^2 V)，常数较小。
- 做法 2：点分治，预处理点分树上每个节点【子树内所有节点到该节点的路径的线性基】，每次查询先求出两点在点分树上的 LCA，再将两个节点到 LCA 的线性基合并（仅需合并一次）。预处理 \text{O}(n\log n\log V)，单次查询 \text{O}(\log n+\log^2 V)，常数大。
- 需要注意的是，在此问题的预处理部分中，点分治的操作只涉及线性基插入，但 ST 表涉及线性基合并，所以树剖做法的复杂度还要再多一个 \log V。

2025-05-10

【其它】\ 对于形如 \sum_{i=1}^{n}\sum_{j=i+1}^{m}f(i,j)（n,m 是定值）这样的求值询问，如果运算 f 满足交换律，一般都能通过运算转换成若干形如 \sum_{i=1}^{p}\sum_{j=1}^{q}f(i,j)（p,q 是定值）这样更好处理的询问。^\text{AtCoder-AGC038\_c}
- 例如：（n<m）\ \footnotesize\boxed{\begin{aligned}\sum_{i=1}^n\sum_{j=i+1}^m\gcd(i,j)&=\sum_{i=1}^n\sum_{j=i+1}^n\gcd(i,j)+\sum_{i=1}^n\sum_{j=n+1}^m\gcd(i,j)\\&=\dfrac1 2\left(\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)-\sum_{i=1}^ni\right)+\left(\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)-\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)\right)\\&=\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)-\dfrac1 2\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)-\dfrac1 2\sum_{i=1}^ni\end{aligned}}
【其它】/【拆贡献】\ 拆贡献：\sum_{i=1}^nf(i)\sum_{d\mid i}g(d)=\sum_{d=1}^ng(d)\sum_{i=1}^{\lfloor\frac n d\rfloor}f(id)
- 也就是说：枚举每个因数被哪些元素计算了贡献，比枚举每个元素的每个因数的贡献要更快。
【数学】/【线性代数】/【线性基】\ 几个关于异或线性基的性质：^\text{【自己推的，需要进一步验证】}
- 线性基的任意两个不同的子集所表示的元素一定不同。
- 任意能被线性基表示的元素在线性基中一定有且仅有一种表示方式。

2025-05-09

【数学】/【线性代数】/【线性基】\ 给定一组线性基 B，选择一个不在线性基中但能被线性基中元素表示的元素 x。令表示 x 的线性基中元素集合为 A，则用 x 替换掉 A 中任意一个元素，得到的集合 B' 仍为一个线性基，且它能表示的所有元素的集合和 B 能表示的集合相同。^\text{洛谷-P4570}
- 推论：无论以何种顺序构造集合 A 的线性基，得到的线性基个数总是固定的。^\text{【自己推的，需要进一步验证】}

2025-05-06

【数学】/【组合数学】/【容斥原理】\ 求互质数对/序列的个数 \rightarrow 数对/序列的总个数-所有元素均为2/3/5/...的倍数的个数+所有元素均为2{\times}3/2{\times}5/3{\times}5/...的倍数的个数-\dots
- 形式化表达：若 n 表示最大的数的大小，\text{cnt}_i 表示所有元素均为 i 的倍数的数对/序列的个数，则答案为\sum\limits_{d=1}^n\left(\mu(d)\sum\limits_{d\mid x}\text{cnt}_x\right)。
【数学】/【数论】/【最大公约数】\ 有关 GCD 的重要性质：若b,r,q\in \mathbf{Z}，则 \gcd(r,b)=\gcd(bq+r,b)。^\text{SPOJ-LCMSUM}
- 它可以拆分成两条性质：
  1. 若b>0，则 \gcd(a,b)=\gcd(a\bmod b,b)
  2. 若 0\leqslant a\leqslant b，则\gcd(a,b)=\gcd(b-a,b)

2025-05-02

【数学】/【快速幂】\ 【数据结构】/【块状数据结构】/【分块思想】\ 常规的快速幂算法时间复杂度为 \text{O}(\log n)，在某些幂询问数量过多的时候仍然不够快。\ 在同一底数（记作 a）与同一模数（记作 m）的条件下，可以利用分块思想，用一定的时间（一般是 \text{O}(\sqrt n)，n 为指数最大范围）预处理后用 \text{O}(1) 的时间回答一次幂询问。^\text{洛谷-P3747}
- 也就是选定一个块长 B，将 a^0,a^1,a^2\dots,a^{B-1} 及 a^0,a^B,a^{2B},\dots,a^{\lfloor\frac{n}{B}\rfloor B} 模 m 后的结果全部预处理出来，于是对于每一次询问可以利用 a^b=a^{\lfloor\frac{b}{B}\rfloor B}\cdot a^{b\bmod B} 实现 \text{O}(1) 求出答案。

2025-05-01

【数学】/【数论】/【中国剩余定理】

CRT 的结论表明：若有同余方程组：\
其中 $n_1,n_2,\dots,n_k$ 两两互质且 $a_i\in[0,n_i)$，\ 则 $a_1,a_2,\dots,a_k$的所有组合与 $[0,n_1n_2\dots n_k)$ 中的数存在**一一映射关系**。 - 通俗地讲：显然，$[0,n_1n_2\cdots n_k)$ 中的每个数模 $n_1,n_2,\dots n_k$ 的结果都只有一种；并且，如果已知一个数模 $n_1,n_2,\dots n_k$ 的值，那么这个数在 $[0,n_1n_2\dots n_k)$ 中必然有且只有一个。（自证不难）这个性质也被叫做“解的独立性”。
因此，令 m=p_1^{k_1}p_2^{k_2}\dots p_s^{k_s} ，则它使得：
- x\equiv a\pmod m\iff\begin{cases}x&\equiv a\bmod p_1^{k_1}\pmod{p_1^{k_1}}\\x&\equiv a\bmod p_2^{k_2}\pmod{p_2^{k_2}}\\&\vdots\\x&\equiv a\bmod p_s^{k_s}\pmod{p_s^{k_s}}\end{cases}
- 设 f(x) 为一个关于 x 的多项式，c(f,a,m) 为满足 f(x)\equiv a\pmod m 且 x\in[0,m) 的正整数 x 的个数，那么有 c(f,a,m)=c(f,a\bmod p_1^{k_1},p_1^{k_1})\cdot c(f,a\bmod p_2^{k_2},p_2^{k_2})\cdots c(f,a\bmod p_s^{k_s},p_s^{k_s})。（自证不难）^\text{BZOJ-2219}
所以，见到模数不是质数的同余方程问题（以及一些计算表达式值的问题），要迅速地想到 CRT 的结论，并将问题转化为模数为素数幂的问题！

2025-04-30

【数学】/【数论】/【原根】\ 【数学】/【数论】/【离散对数】

众所周知，令 m 的原根为 g，则 \{g^0,g^1,\dots,g^{\varphi(m)-1}\} 恰是 [1,m-1] 中所有与 m 互质的数的集合。\ 因为有这个性质，所以很多情况下（尤其是 m 为质数时），我们可以将 x^a\equiv b 这类问题中的 x 和 b 分别表示为 g 的幂次的形式，从而将问题挪到指数上，变成易解决的线性同余方程等问题。^\text{CodeForces-1106F}

2025-04-29

【数据结构】/【块状数据结构】/【分块思想】\ BSGS 算法本质上是一种类似于分块的折半枚举，这种方法可以推广到一类“找关键元素”的问题中。^\text{洛谷-P3306}\ 考虑下面这种问题：

给一个长度为 n 的数组 a，已知首个元素 a_0 的值，且 a 的任意相邻两项元素之间都满足某种固定的关系，记作 a_{i+1}=f(a_i)。求元素 x 在数组中首次出现的位置。
关系 f 是可逆的，即对于任意元素 i，最多有一个元素 j 满足 i=f(j)。并且要求可以快速求逆。

对于这种问题，可以先设一个块长 B=\text O(\sqrt n)，预处理出 a_0,a_B,a_{2B},\cdots,a_{\lfloor\frac{n}{B}\rfloor B} 的值并存进哈希表（例如 u_map），然后从 x 开始往前跳 f^{-1}。如果有解，那么跳最多(B-1)次一定会碰到哈希表里的值。这样就可以求出答案了。

2025-04-28

【数学】/【数论】/【欧拉函数】\ 对于任意正整数 n>2，\varphi(n) 总是偶数。^\text{CodeForces-906D}^\text{洛谷-P3747}
- 证明：
  1. 由于\gcd(i,n)=\gcd(n-i,n)，所以对于任意 1\leqslant i<\dfrac n 2，i 和 (n-i) 要么都与 n 互质，要么都不与 n 互质。
  2. 由于 n>2，所以 n 不与自身互质。
  3. 若 n 是偶数，由于 n>2，所以 n 与 \dfrac n 2 不互质。
  4. 综上，[1,n] 中与 n 互质的正整数的个数一定为偶数。
- 推论：该循环的时间复杂度为 \text{O}(\log n)：
```
for(int i=n;i>1;i=phi[i]){
/*...*/
}
```
  换句话说，从一个数 n 开始跳 \varphi 一直跳到 1，跳的总次数只有 \text{O}(\log n) 次。
  
  证明：对于任意偶数 n 一定有 \varphi(n)\leqslant\dfrac n 2。

2025-04-27

【数学】/【数论】/【分解质因数】\ 给一个数 n 分解质因数有两种方法。
- 使用常规做法，即把 2 ~ \sqrt n 的所有数都扫一遍，把其中 n 的质因数一个个分离出来。\ 单次\text{O}(\sqrt n)，适用于需要分解质因数的次数较少（通常不超过 \text{O}(\log n)）的情况。
- 事先把 1 ~ n 的所有质数用线性筛筛一遍，一边筛一边维护所有数的最小质因数。（线性筛中，每个数只被最小质因数筛掉，所以这个非常容易维护）这样，对 2 ~ n 中的任意一个数分解质因数的复杂度就降到 \text{O}(\log n) 了（每次跳最小质因数就行）。\ 预处理 \text{O}(n)，单次分解质因数 \text{O}(\log n)。适用于需要为大量正整数分解质因数的情况。使用的前提是时间复杂度支持 \text{O}(n)。

2025-04-26

【数学】/【数论】/【乘法逆元】\ 【数学】/【数论】/【费马小定理】\ 【数学】/【数论】/【最大公约数】/【扩展欧几里得算法】\ 求一个数 a 模 m 意义下的逆元（\gcd(a,m)=1）：
- 当 m 是质数时，用费马小定理
- 当 m 不是质数时，用 exgcd
时间复杂度均为单次\text{O}(\log m)。

2025-04-21

【其它】\ “关键点优化”用于解决一类区间内合法子区间数量统计问题。\ 其做法是对于所有长度为 l 的子区间，将整个区间中下标为 l 的倍数的位置标记为关键点。由于每个长度为 l 的子区间一定覆盖恰好 1 个关键点，所以我们就将这些区间按关键点分好了组，可以批量合并处理同一个关键点对应的所有子区间。这样，设整个区间的长度为 n，那么覆盖所有子区间的时间复杂度就从 \text{O}(n^2) 降至了 \text{O}(n\log n)（调和级数）。\ 这种优化适合处理下面的问题：
- 一个子区间合法的条件是没有覆盖任何不合法的位置。一个位置对于某个子区间而言是否合法，仅和这个子区间的长度有关。此外，如果子区间长度是定的，我们能够快速找到一个位置前面（及后面）第一个不合法的位置，但我们无法通过遍历整个区间统计这个长度的合法子区间的数量。^\text{洛谷-P1117}
【其它】\ 在很多合法元素数统计类问题中，优化一个做法常常需要将所有元素进行分类并对每一类批量统计答案。分类的方式有时不止一种，当一种分类方式难以批量求解的时候，要发散地想想其他的分类方式。
- 例如：在这个问题^\text{洛谷-P1117}中，要统计区间中以每个位置开头（结尾）的“AA子串”数量。这时，由于长度相同的“AA子串”具有一些便于处理的性质（若一个位置不合法则所有覆盖该位置的区间都不合法），所以处理时应该按长度分类处理，而不是按区间开头（结尾）。

2025-04-18

【算法基础】/【二分】/【二分答案】\ 当看到题目中出现“求某些元素的【两（常数）个属性的最小值】的最大值”（或较大值的最小值）这一类询问时，也要想到二分答案。^\text{洛谷-P4094}
- 这种“若干属性最小值的最大值”询问因为各个元素的贡献完全独立、无法合并，所以很难在单次 \text{O}(n) 以下的时间复杂度下直接求。但是如果用二分答案校验（它显然是满足单调性的）最大值是否大于等于 k，那问题就转化成了“是否存在元素所有属性都大于等于 k”，这样就可以合并求了。

2025-04-12

【字符串】/【AC 自动机】\ 只有模式串需要加进 AC 自动机。对于文本串，只需要标记它在AC自动机上跳到的点即可，不需要加进 AC 自动机。\ （注：求串 t 在串 s 中的出现次数时，t 就是模式串，s 就是文本串）^\text{洛谷-P5840}
【图论】/【树上问题】/【树基础】\ 如果将一棵树上的一些节点 u_1,u_2,\cdots,u_k 按照 DFS 序排序，\ 那么 \forall1<i\leq k, 总有 \forall1\le j<i,\text{dep}(\text{lca}(u_j,u_i))\leq\text{dep}(\text{lca}(u_{i-1},u_i)).^\text{洛谷-P5840}
- 通俗地讲1：如果这棵树的 DFS 序是将树按照“根-左-右”的顺序遍历得到的，那么u_i总是在u_{i-1}的下方或右侧。
- 通俗地讲2：如果将 u_1,u_2,\cdots,u_{i-1} 中每个点到根的路径上的所有点做标记，那么从 u_i 开始往上走，走到的第一个被标记的点一定在 u_{i-1} 到根的路径上。

2025-04-10

【算法基础】/【二分】/【二分答案】\ 当看到题目中出现“满足条件的最大/最小”要立刻警觉地想到二分答案。^\text{Gym-102394A}
【图论】/【树上问题】/【树基础】\ DFS 序可用于快速判断一个节点是否在某个有根树的子树内。^\text{洛谷-P2414}
【其它】\ 有一些静态区间查询问题贡献计算比较复杂，难以直接用前缀和、线段树等维护。这种情况下，如果问题支持离线，那么可以将询问按询问右端点排序，并对每个右端点维护贡献随左端点的变化情况。（当然，如果强制在线可以采用可持久化数据结构维护）
- 例1：给定长为 n 的数组 a，有 q 组询问，每次询问区间 [L,R] 中有多少个不同的数。（1\le n,q\le10^5）^\text{洛谷-P5840}
- 例2：给定长为 n 的数组 a，有 q 组询问，每次询问区间 [L,R] 的最小公倍数取模后的结果。（实质上是求【每个质因数【在一段区间每个数质因数分解中的幂次的最大值】的乘积】）（1\le n,q,a_i\le10^5）^\text{CodeForces-1422F}
- 前缀线性基也是这种思想的应用。
- 前面提到的这种问题通常都是不可合并的多次询问问题。其中有很多问题其实都可以用分块、莫队等方法解决。

2025-04-09

【数学】/【组合数学】/【容斥原理】\ 求至少存在 1 个……的方案数 \rightarrow 求不存在……的方案数^\text{洛谷-P4052}

2025-03-31

【语言基础】/【C++ 标准库】/【STL 容器】/【序列式容器】/【vector】\ 不要在一个语句中同时插入、访问一个 vector！！！因为插入可能导致 vector 的内存地址发生偏移。^\text{洛谷-P3834}