本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-29 19:41:02

保证本文中笔者贡献不高于 GenAI。
保证本文中批话占比不低于 20%。

CSP-S：

请勿指责，已被 Pigsyy 彻底击败，自身实力尚有不足，故不打算撰写游记。

NOIP 前一天：

下午抵达淄博后，立即投入模板练习，但面对缩点、割点、二边连通分量等概念仍感困惑，不禁自嘲基础薄弱。
晚间进行试机准备，认真调试了线段树模板。随后，我进行了如下操作（此前一直未明确 Linux 的具体位置）：

• 首先根据老师指引找到虚拟机软件，在左下角菜单中搜索以 V 开头的程序，成功定位。
• 启动虚拟机后，打开 CodeBlocks 编辑器，编写测试代码并尝试编译，经过摸索最终顺利完成。

试机流程按计划结束，随后休息。虽感自身水平有待提升，但仍需调整心态迎接明日挑战。

NOIP：

开题。
T1 初步尝试后迅速调整思路，冷静处理后成功通过，此时已耗时近一小时。出考场后得知多数人仅用数分钟便解决 T1，不禁感叹自身差距。
T2 经过约数小时严谨推导，得出 $\Theta(n^3)$ 解法，但因实现复杂度较高而放弃，转而争取部分分数。
T3、T4 获得常规得分。
整体表现平平，再次反思自身不足。出考场后发现 KSCD_ 成绩显著领先，更感自身需提升。
返家后查阅资料，发现 T4 实为一道曾做过的题目之强化版本，原题可获 85 分，对此深感遗憾。

:::::success[总结] 我咋这么菜。
:::::

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-26 22:31:29

:::::info[题目基本信息] 考察：搜索，图论（中下位紫？）。
题目简介：
给定 $n$，有 $n$ 个物品，价值为 $\{w_n\}$，两端（可以钦定哪端是首段，哪端是尾端）颜色分别为 $\{s_n\},\{t_n\}$，现在你需要选取一些物品，将它们按任意顺序排列，将它们拼接，要求拼接的相邻物品中前一个物品的尾端颜色和后一个物品的首端颜色相同，你的得分就是选取的物品的价值总和，问得分最大是多少。
数据范围：

• $1\le n\le 5\times 10^5$
• $\forall i\in[1,n],1\le w_i\le 1000$
• $\forall i\in[1,n],1\le s_i,t_i\le\color{red}4$ ::::: 见二连边还在追我，容易想到对于每一个物品连一条 $s_i\leftrightarrow t_i$ 的边，然后你观察到里面有很多很多的重边，考虑怎么利用。
  有一个比较重要的性质：
• $\forall u,v$，$u$ 和 $v$ 之间的无向边在两点均可达时可以两两缩成一个点的自环，直到还剩最多两条边。
  :::::success[证明] 这个性质是比较显然的。因为两条边就足够你来回一次了，剩下的边自然可以缩成一个自环单独处理。
  ::::: 然后我们注意到对于所有可达点自环都能被记进贡献内（注意当原图就有多条自环时同样需要根据上面方式保留最多两条边），然后发现对于剩下的边我们可以直接爆搜，于是就有了下面的算法流程：
• 枚举点集子集，使用并查集判断它们是否联通，若不联通枚举下一个子集。
• 对于一个子集先累加自环贡献，然后对于剩余的边直接爆搜所有路径即可。

:::::success[优化] 在爆搜中，对于一个点，我们对于通向同一个点的边只选择价值最大的那条递归，容易证明正确性，实测运行时间缩小到原来的 $\dfrac{1}{60}$。
::::: 这样我们就做完了此题。
时空复杂度玄学。

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-25 22:27:32

:::::info[题目基本信息] 考察：动态规划 DP（个人认为是紫，也可能是我太菜了）。
题目简介：
给定 $\{op_n\}$，值域为 $\{0,1,2,3\}$，问有多少 $n$ 阶排列满足（对 $998244353$ 取模）：

• $\displaystyle\forall i\in(1,n],op_i=0\Rightarrow a_i<\min_{j=1}^{i-1}a_j$
• $\displaystyle\forall i\in(1,n],op_i=1\Rightarrow a_i>\max_{j=1}^{i-1}a_j$
• $\displaystyle\forall i\in[1,n),op_i=2\Rightarrow a_i<\min_{j=i+1}^na_j$
• $\displaystyle\forall i\in[1,n),op_i=3\Rightarrow a_i>\max_{j=i+1}^na_j$

数据范围：

• $1\le n\le 5000$
• $\forall i\in[1,n],op_i\in\{0,1,2,3\}$ ::::: 对于排列，套路地上连续段 DP，套路地设 $f_{i,j}$ 表示考虑到 $a_{pos}\in[1,i]$ 的所有 $pos$，它们形成了 $j$ 个连续段，至于状态细节不必管，反正最后我尝试的状态都寄了。
  那咋办？！？！？！
  :::::info{open} 不只尝试改变连续段的定义，还要尝试改变连续段定义于的对象。谁告诉你连续段 DP 只能对值域 DP 的？
  切记 DP 题不是套板子题。
  如果你看不懂下面的内容就在心里默念：连续段 DP 是在相对位置上进行 DP，并手玩验证每一种方案都能构造出实例。 ::::: 尝试改变状态的定义，设 $f_{i,j}$ 为考虑到 $[1,i]$ 的所有 $pos$，未被考虑的位置可以在 $j$ 个值域连续段（中间没有已填位置的段）填，先判掉无解情况（存在一个 $2$ 位于 $0$ 左边或者存在一个 $3$ 位于 $1$ 左边），接下来分类讨论：
• $op_i\in\{0,1\}$：
  这时该元素不会对后面的元素造成影响，还会凭空增加一个连续段，所以 DP 数组会整体平移。
• $op_i\in\{2,3\}$：
  这时手玩发现这个位置左右至少有一边位置不能填了，这样会使连续段数量变少（可以不变），所以 DP 数组会整体求后缀和。

按上述简单实现可以通过。
时间复杂度为 $\Theta(n^2)$，空间复杂度为 $\Theta(n)$。

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-24 21:41:34

:::::info[题目基本信息] 考察：Kruskal 重构树，并查集，动态规划 DP（$3189$）。
题目简介：
给定一个 $n$ 个点 $m$ 条边的无向联通图，你可以在这个图上任意选起点任意游走，唯一的限制是给定序列 $\{a_n\}$，当你在 $u$ 点时你的能力值不得小于 $a_u$。
现在你的任务是在每个节点都操作一次，当你位于 $u$ 点时你可以对 $u$ 点进行操作，操作后你的能力值会减少 $b_u$，当你能力值小于 $0$ 时任务立即失败（即使你操作了最后一个点），问任务成功需要的最低初始能力值是多少。
数据范围：

• $1\le n\le 10^5$
• $n-1\le m\le 10^5$
• $\forall i\in[1,n],1\le a_i,b_i\le 10^9$ ::::: 先令 $a_u\leftarrow\max(a_u-b_u,0)$，限制转化为你在任一时刻位于点 $u$ 时能力值均不能低于 $a_u$。
  你考虑 $u$ 到 $v$ 如何才能最可能走过去，设 $u$ 和 $v$ 之间的一条路径为 $P$，当前能力值为 $p$，那么充要条件就为 $\max_{u\in P}a_u\le p$，现在我们就是尽可能得让这个值变小。
  让 $\max$ 变小我们可以考虑使用 Kruskal 重构树，但是现在是点权，所以我们考虑给所有的 $u$ 和 $v$ 连一条边，边权为 $\max(a_u,a_v)$，这样就可以跑最小生成树。
  考虑贪心，按 $a_u$ 从小到大枚举点 $u$，在和它相连的比 $a_u$ 小的点 $v$ 中没连的点令其与 $u$ 连边，正确性易证。
  这样我们建出了一棵最小生成树，但是通过尝试我们发现它的性质还是不够好，我们仍然无法解决这个问题。
  下面就是这个题非常妙的转化，我们将上面的建树方式转化为：

按 $a_u$ 从小到大枚举点 $u$，在和它相连的比 $a_u$ 小的点 $v$ 中没连的点令其最高的祖先与 $u$ 连边。

虽然看起来很人类智慧，但是正确性是成立的，因为与 $v$ 直接相连或间接相连的点 $w$ 的 $a_w$ 肯定都不超过 $a_u$，同时这条 $v$ 到 $w$ 路径上的权值肯定都不超过 $a_u$，所以点权 $\max$ 是不变的，正确性成立。
那么这样建树有没有什么其他性质呢？

• 性质：若以 $a_i$ 最大的 $i$ 为根，那么对于任意 $u,v$，若 $u$ 是 $v$ 的祖先，那么 $a_u>a_v$。证明显然。

那么有了这个重要性质这个题就可做了，容易发现本题在哪里选起点都无所谓，钦定从根开始，设 $f_u$ 表示以 $u$ 为根的子树中从 $u$ 开始操作完所有子树内的点（不必回到 $u$ 点）的最小初始能力值。那么对于一个 $u$，枚举最后进入的子树的根为 $v$，那么遍历其它子树时由于上面所说性质，我们只需保证最后一次回到 $u$ 时的能力值不低于 $a_u$ 即可，容易得到状态转移方程：
$$f_u=\min_{v\in\text{son}_u}(siz_u-siz_v+\max(a_u,f_v))$$ 其中 $siz_u$ 表示子树 $u$ 内的 $b_i$ 总和，$\text{son}_u$ 表示 $u$ 的儿子集合，特别地，对于叶子结点 $u$，满足 $f_u=a_u+b_u$。
这样我们直接 DP 就做完了这道题。
时空复杂度均为 $\Theta(n+m)$。

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-23 16:36:09

:::::info[题目基本信息] 考察：笛卡尔树，数学，贪心（个人认为上位紫）。
题目简介：
给定序列 $\{a_n\}$，有一个序列 $\{b_n\}$ 初始全为 $0$，你有两种操作：

• 选择一个整数 $k\in[1,n]$，进行操作 $\forall i\in[1,k],b_i\leftarrow b_i+1$，代价为 $k$。
• 选择一个整数 $k\in[1,n]$，进行操作 $\forall i\in[k,n],b_i\leftarrow b_i+1$，代价为 $n-k+1$。

问最后要使得 $\forall i\in[1,n],b_i\ge a_i$ 的最小代价是多少。
数据范围：

• $1\le n\le 10^6$
• $\forall i\in[1,n],0\le a_i\le 10^9$ ::::: 从全 $0$ 序列转化成 $\{b_n\}$ 不方便我们研究 $\{b_n\}$ 的性质，所以我们考虑把过程倒过来，从 $\{b_n\}$ 转化成全 $0$ 序列，然后将操作变为前后缀减 $1$。
  考虑一下差分，如果 $b_i>b_{i+1}$，那么我们至少要在 $i$ 这个位置进行 $b_i-b_{i+1}$ 次前缀减 $1$ 操作，这时序列变成单调不递减序列，那么只需要令 $b_1\ge 0$ 即可满足条件。
  但是我们只考虑前缀减不考虑后缀减是否有正确性？
  虽然感性理解很有正确性，但是我们还是严谨证明它。
  :::::success[证明]{open} 把上面那段文字转化成数学语言就是 $\displaystyle b_1\ge\sum_{i=1}^{n-1}\max(0,b_i-b_{i+1})$，类似地可以得到后缀和的式子 $\displaystyle b_n\ge\sum_{i=1}^{n-1}\max(0,b_{i+1}-b_i)$，这两者是否等价？
  设 $b_0=b_{n+1}=inf$（$inf$ 是一个足够大的值，但不是 $+\infty$，否则无法比较大小），那么上述式子可以转化为 $\displaystyle b_0\ge\sum_{i=0}^n\max(0,b_i-b_{i+1})$ 以及 $\displaystyle b_{n+1}\ge\sum_{i=0}^n\max(0,b_{i+1}-b_i)$，容易发现两个等式左右两部分相等，所以这两个式子等价。
  ::::: 为方便我们将上面两式相加（其实不搞也可以推），得到：
  $$\sum_{i=0}^n|b_i-b_{i+1}|\le 2inf$$ 现在我们需要从 $\{a_n\}$ 数组通过不断进行单点加 $1$ 操作使得满足上面的条件，通过手玩发现减少上面的值的唯一基础操作就是通过给满足以下条件的 $[l,r]$ 区间加 $1$：
• $\forall i\in[l,r),a_i=a_{i+1}$
• $a_{l-1}>a_l\land a_r<a_{r+1}$

这时，它会对上面的值贡献 $2$。
所以我们贪心考虑快速找到序列中的最短的极长内凹相等连续段，这个我们建出笛卡尔树，然后把每个子树按子树大小排到桶里存储它们能操作的次数，循环减少值即可。
这样我们就做完了这道题。
时空复杂度均为 $\Theta(n)$。

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-23 10:39:50

:::::info[题目基本信息]{open} 考察：贪心，哈希 Hashing，STL，离线处理（省选/NOI-）。
题目简介：
给定一棵树，有 $n$ 个结点，以 $1$ 为根，每个点有点权，$q$ 次询问，每次询问给定序列 $\{s_{len}\}$，设 $ans_i$ 为 $1$ 到 $i$ 的简单路径上所有点的点权按顺序排列构成的序列最多能划分成的部分数使得每部分中都包含 $\{s_{len}\}$ 子串（下文简称匹配），求 $\displaystyle\max_{i=1}^nans_i$ 的值。保证 $len$ 的总和不超过 $10^5$。
数据范围：

• $1\le n,q,len\le 10^5$
• $\forall i\in[1,n],1\le a_i\le n$
• $\forall i\in[1,len],1\le s_i\le n$ ::::: 先考虑一个序列和另一个序列匹配的答案怎么求，有一个显然的贪心，就是从左往右扫，能匹配就匹配，感性理解正确性成立，可以归纳证明。
  那么我们先考虑暴力，对于每个串都 DFS 一遍，对于每个节点都贪心地看以它为末尾的子串能否匹配（这个可以使用哈希实现，预处理维护每个节点到根的序列哈希即可），可以匹配就从 $len$ 级祖先转移过来，否则就从父亲转移，精细实现可以做到 $\Theta(qn)$。
  我们观察得到每一个串，与它匹配的节点数并不多，因为以每一个节点结尾的长度为定长的字符串是唯一的，这启发我们把询问离线下来，考虑对于每一个长度分别考虑，先通过并查集等方式将询问串相同的询问合并，然后使用 map 存储每个串对应的编号，然后开两个数组 $f$ 和 $g$ 分别表示编号为定值的答案和上一个转移的点是什么，这样我们就可以判断一个点能否更新了，更新时再把答案也一并更新，只需要 DFS 一遍同时回溯就可以处理了。
  常数较大，需要卡常，精细实现可以通过本题。
  时间复杂度为 $\Theta(n\sqrt V\log q)$（$V$ 为 $len$ 的值域），空间复杂度为 $\Theta(n+q+V)$。

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-22 19:32:17

:::::info[闲话]{open} 来一篇严谨证明题解！ ::::: :::::info[题目基本信息] 考察：Dilworth 定理，线段树（提高+/省选-）。
题目简介：
给定 $\{s_n\},\{c_n\}$，定义 $a$ 可以包含 $b$ 当且仅当 $s_a\le c_b$，对于每一个 $k$，询问对于 $[1,k]$ 内的所有整数，每个整数可以钦定它包含最多一个数，问最少有几个数不被其它数包含。
数据范围：

• $2\le n\le 2\times 10^5$
• $\forall i\in[1,n],1\le c_i<s_i\le 10^9$ ::::: 我们定义 $a\preceq b$ 表示 $a$ 可以包含 $b$ 或 $a=b$，然后我们对下面的性质做证明：
• 自反性：$a\preceq a$。 :::::success[证明] 根据定义容易得出。
  :::::
• 反对称性：$a\preceq b\land b\preceq a\Rightarrow a=b$。 :::::success[证明] 考虑证明它的逆否命题 $a\ne b\Rightarrow a\npreceq b\lor b\npreceq a$，考虑反证证明 $a\ne b\land a\preceq b\land b\preceq a$ 不成立，我们可以得到 $s_a\le c_b<s_b\le c_a<s_a$，显然不成立。 :::::
• 传递性：$a\preceq b\land b\preceq c\Rightarrow a\preceq c$。 :::::success[证明] 若 $a=b\lor b=c$，那么等量代换一下显然成立。
  否则我们得到 $s_a\le c_b<s_b\le c_c$，进一步得出 $a\preceq c$。
  ::::: 那么 $a\preceq b$ 是偏序，设偏序集为 $S=[1,k]\cap\mathbb Z$，那么我们应用 Dilworth 定理（参考 oiwiki，但给出了自认为更严谨更详细的证明）。
  :::::success[Dilworth 定理] $S$ 的最长反链等于最小链覆盖数。
  ::::: :::::success[证明] 考虑数学归纳法。
  若 $|S|\le 3$，暴力枚举验证发现确实成立。
  假设偏序集大小小于 $|S|$ 的偏序集均成立，若 $S$ 内的元素两两不可比（$\forall u,v\in S,u\ne v\Rightarrow u\npreceq v\land v\npreceq u$），那么命题显然成立，否则取一条长度不为 $1$ 的链 $P$，设最小元（$\forall p\in P,v\preceq p$）为 $v$，最大元（$\forall p\in P,p\preceq v$）为 $V$。
  再设 $T=S\backslash\{v,V\}$，如果 $T$ 的最长反链小于 $S$，那么由于 $v\preceq V$ 所以两者不位于同一反链，那么最长反链长度为 $S$ 的最长反链长度减 $1$，那么根据假设 $T$ 的最小链覆盖数等于最长反链，那么由于 $S$ 到 $T$ 扔掉了两个点，那么 $S$ 的最小链覆盖数会等于 $T$ 的最小链覆盖数加 $0,1$ 或 $2$。
• 不会是 $2$：
  若 $S$ 的最小链覆盖数等于 $T$ 的最小链覆盖数加 $2$，那么将 $T$ 的最小链覆盖加上一条 $\{v,V\}$ 就会得到更小的链覆盖数，产生矛盾。
• 不会是 $0$：
  若 $S$ 的最小链覆盖数等于 $T$ 的最小链覆盖数，传递一下得到 $S$ 的最小链覆盖数等于 $S$ 的最长反链长度减 $1$，但是 $S$ 的这条反链内的元素一定两两不位于一个链，产生矛盾。

故 $S$ 的最小链覆盖数等于 $T$ 的最小链覆盖数加 $1$，传递得到 $S$ 的最小链覆盖数等于 $S$ 的最长反链长度，故在这种情况下命题成立。
当 $T$ 的最长反链等于 $S$ 的时，找到 $T$ 的最长反链 $P$，设集合 $S^-=\{x\in S|\exists p\in P,x\preceq p\},S^+=\{x\in S|\exists p\in P,p\preceq x\}$，那么有以下性质：

• $S^-\cup S^+=S$，否则存在一个元素与 $P$ 内元素不可比，那么 $P$ 还能加入这个元素变得更长。
• $S^-\cap S^+=P$，由偏序集的传递性（若 $\exists p_1,p_2\in P,p_1\ne p_2,p_2\preceq x\preceq p_1$，根据传递性马上就能推出矛盾）和自反性（若 $\exists p\in P,p\preceq x\land x\preceq p$，马上就能推出 $x=p$）容易得出。
• $|S^-|,|S^+|<|S|$，因为 $V\notin S^-$（否则与最大元条件矛盾，下同）且 $v\notin S^+$。

对 $S^-,S^+$ 应用归纳假设，然后就得出了 $S^-$ 和 $S^+$ 的 $S$ 的最小链覆盖数条链，同时每条链都包含了 $P$ 内的一个元素，将 $S^-$ 和 $S^+$ 的最小链覆盖内的链一一对应拼接即可构造。
证毕。 ::::: 好的我们将这个问题转化为最长反链，我们注意到对于 $i,j$，它们不能互相包含当且仅当 $(c_i,s_i]$ 和 $(c_j,s_j]$ 有交集，然后我们每次在线段树上对 $(c_i,s_i]$ 区间加 $1$ 查询全局最大值即可。
然后我们就做完了此题。
时间复杂度为 $\Theta(n\log n)$，空间复杂度为 $\Theta(n)$。

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-22 16:36:24

:::::info[闲话] 模拟赛 T2，不会做（其实 T1 也不会），菜完了。
::::: :::::info[题目基本信息] 考察：数学，组合数学，动态规划 DP（个人认为中下位紫）。
题目简介：
给定 $\{a_n\},\{b_n\}$ 及常数 $k$，$q$ 次询问，每次询问给定 $x,y$，求当 $a_{n+1}=x,b_{n+1}=y$ 时有多少有序数对集合 $S$ 满足（对 $10^4+9$ 取模）：

• $|S|=k$
• $\forall(x_1,y_1),(x_2,y_2)\in S,(x_1,y_1)\ne (x_2,y_2)\Rightarrow x_1\ne x_2\land y_1\ne y_2$
• $\forall(x,y)\in S,\exists i\in[1,n+1],x<a_i\land y<b_i$

数据范围：

• $1\le n,q\le 10^5$
• $1\le k\le 30$
• $\forall i\in[1,n],1\le a_i,b_i\le 10^5$
• $1\le x,y\le 10^5$ ::::: 由于个人习惯，我们令 $a_i\leftarrow a_i-1,b_i\leftarrow b_i-1$，这样上面 $x<a_i\land y<b_i$ 的条件就可以取等了。
  把图画出来：
  
  注意到这些点位置合理的充要条件是位于这些红线（最高的一条，横坐标为 $i$ 的最上方的一条的纵坐标设为 $mx_i$）的下方，那么这就是经典 trick：从限制紧的部分开始决策，这样前面的决策一定会限制后面的决策，那么对于没有新加点的情况，我们容易设出如下 DP：
  设 $f_{i,j}$ 表示从右往左考虑到横坐标为 $i$ 的一列，选择了 $j$ 个点的方案数，那么容易得到状态转移方程：
  $$f_{i,j}=f_{i+1,j}+f_{i+1,j-1}\cdot\max(0,mx_i-j+1)$$ 这是没有新加点的情况，做 $q$ 次能得到 $\Theta(Vqk)$ 的时间复杂度，能过 $55$ 分。
  考虑新加一个点，画图可知它会覆盖中间连续的一段 $mx_i$，那么我们可以考虑把前后缀分别处理再拼起来。
  再设 $g_{i,j}$ 表示从左往右考虑到横坐标为 $i$ 的一列，从第 $i$ 列向右（包括该列）选择了 $j$ 个点的方案数，容易类比得到状态转移方程：
  $$g_{i,j}=g_{i-1,j}+g_{i-1,j+1}\cdot\max(0,mx_i-j)$$ 现在我们预处理好了 $f$ 和 $g$，现在将它们拼起来，首先容易二分出未被覆盖的部分和被覆盖的部分的分界点（为方便 $f$ 的分界点设为 $p$，$g$ 的分界点设为 $q$），然后枚举 $j_f$ 和 $j_g$ 分别表示 $f$ 和 $g$ 的第二维分别是多少，这样还有 $q-p+1$ 列可以填，选择 $j_g-j_f$ 列，容易得到这一种的贡献：
  $$f_{p+1,j_f}g_{p-1,j_g}\binom{q-p+1}{j_g-j_f}(b-j_f)^{\underline{j_g-j_f}}$$ 全部累加起来即可，精细实现即可通过本题。
  时间复杂度为 $\Theta(n+Vk+qk^2)$，空间复杂度为 $\Theta(Vk)$。

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-21 20:57:13

:::::info[题目基本信息] 考察：图论，欧拉回路（$2300$）。
题目简介：
给定序列 $\{a_n\},\{b_n\}$，判断是否 $n$ 阶排列 $\{p_n\}$ 满足以下条件，若存在构造一种方案：

• $\forall i\in[2,n],a_{p_i}=a_{p_{i-1}}\lor b_{p_i}=b_{p_{i-1}}$
• $\forall i\in[3,n],(a_{p_{i-2}}\ne a_{p_{i-1}}\lor a_{p_{i-1}}\ne a_{p_i})\land(b_{p_{i-2}}\ne b_{p_{i-1}}\lor b_{p_{i-1}}\ne b_{p_i})$

数据范围：

• $1\le n\le 2\times 10^5$
• $\forall i\in[1,n],1\le v_i,p_i\le 10^9$
• $\forall i,j\in[1,n],i\ne j,a_i\ne a_j\lor b_i\ne b_j$ ::::: 见二建图还在追我，先对 $\{a_n\}$ 和 $\{b_n\}$ 离散化，然后接下来把它们分别看成一个二分图的左部点和右部点，然后这 $n$ 个对就是 $n$ 条边，那么我们要求的就是这个二分图的欧拉路径。
  首先需要保证这个图联通并最多有两个点度数为奇数，然后跑 Hierholzer 算法。
  :::::success[Hierholzer 算法简介] 先讨论欧拉图（寻找欧拉回路）的情况，因为半欧拉图（寻找欧拉路径）的情况可以在两个度数为奇数的点之间连一条边转化为欧拉图情况。
  一个图是欧拉图有一条等价转化：整个图可以被拆解成若干个不共边的回路（仅讨论连通图）。
  ::::success[证明]
• 是欧拉图推拆解回路：
  众所周知，欧拉图的所有点度均为偶数，那么我们随便取一个度不为 $0$ 的点 $u$，随便找到一个与其相连的边 $(u,v)$ 并删除它，那么这时整个图有两个点度为奇数，这时递归 $v$ 也一定能找到一条与其相连的边，这样递归下去直到回到点 $u$，这时我们找到了一个回路，不断操作，最终能删空图，命题也证毕。
• 拆解回路推是欧拉图：
  考虑合并这些回路，随便取两个回路，若两个回路共点直接合并，否则由于整个图联通，那么这两点间必定有一条路径，这条路径上的边肯定都属于一个回路，故一定有方法合并这两个回路，证毕。 :::: 好的，那么我们根据上述拆解回路推是欧拉路的证明我们容易得到 Hierholzer 算法的具体流程：先从一个点开始找到一条回路，然后在该回路周围找到一个共点回路合并它们即可。
  这个过程实际可以使用 DFS 实现，具体实现见代码。
  最终时间复杂度为 $\Theta(n+m)$。
  ::::: 这样我们就做完了这道题。
  时间复杂度为 $\Theta(n\log n)$，空间复杂度为 $\Theta(n)$。

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-21 10:48:57

:::::info[闲话] ::::: :::::info[题目基本信息] 考察：基环树，组合数学，Ad-hoc（$2800$）。
题目简介：
给定序列 $\{a_n\}$，你可以进行若干次下面的操作：

• 选择一个 $i\in[1,n]$，交换 $a_i$ 和 $a_{a_i}$。

问最终能得到的序列个数对 $10^9+7$ 取模的结果。
数据范围：

• $1\le n\le 10^6$
• $\forall i\in[1,n],1\le a_i\le n$ ::::: 闲话里已经透露了，套用经典建图 trick，我们可以建图连边，连出 $i\rightarrow a_i$ 的一条边，形成了一个 $n$ 个点 $n$ 条边的内向基环树森林。
  我们考虑观察操作前后图的变化，原来的图有 $i\rightarrow a_i\rightarrow a_{a_i}$，现在操作后交换了 $a_i$ 和 $a_{a_i}$（下文简称操作 $a_i$），那么变成了 $i\rightarrow a_{a_i}$ 以及 $a_i\rightarrow a_i$。
  我们观察到若一个点连成了一个自环，那么再次操作它会无效，我们为方便最后的计数钦定不能再操作这个点。
  但是我们观察到图的改变会对我们的计数带来很大的麻烦，所以我们不妨不改变图的形态，只给 $i\rightarrow a_i$ 这条边打一个标记，那么通过标记我们能否还原最终的 $\{a_n\}$ 序列？
  答案是肯定的：
• 若点 $u$ 存在一条入边被打标记，那么点 $u$ 已经被操作过，$a_u=u$。
• 否则，我们从点 $u$ 开始，不断走它的出边，直到找到一条没有被打标记的边，它的出点 $v$ 就是 $a_u$。

容易发现每个合法标记序列能够唯一映射到一个 $\{a_n\}$ 序列，由于每个点最多有一条入边被打标记那么答案上界就是 $\displaystyle\prod_{i=1}^nind_i+1$，其中 $ind_i$ 是 $i$ 点的入度。
那么这是否就是答案？
这并不是。
举个例子，一个环上的边全部标记就不合法，因为你在打最后一条边的标记时 $a_u$ 已经全部等于 $u$，无法再操作，也就是说一个环上只有一条边未被操作时不能再对环上的点进行操作了，那么枚举环上的点 $u$，操作 $u$ 的可能性有 $ind_u$ 种，那么可能就会有 $\displaystyle\sum_{u}ind_u$ 种不合法的标记序列了。
那么最终我们就得到了答案的式子：
$$(\prod_{cycle\in\text{cycles}}(\prod_{u\in cycle}ind_u+1)-(\sum_{u\in cycle}ind_u))\cdot(\prod_{u\notin\text{cycles}}ind_u+1)$$ 这样我们就做完了这道题。
时空复杂度均为 $\Theta(n)$。

code