本文章由 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-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-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-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-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-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-10-28 15:22:26

:::::info[题目基本信息] 考察：分块，Lucas 定理，动态规划 DP（NOI/NOI+/CTSC）。
题目简介：
给定 $\{a_n\}$，$q+n$ 次操作，操作分为两类：

1. 给定 $l,r$，进行操作 $\forall i\in(l,r]$，同时令 $a_i\leftarrow a_i\oplus a_{i-1}$。
2. 给定 $pos$，求 $a_{pos}$ 的值。

其中操作满足条件：$\forall i\in[1,n]$，第 $q+i$ 次操作都是第二种操作，且 $pos=i$。
数据范围：

• $1\le n\le 2.5\times 10^5$。
• $1\le q\le 10^5$。
• $\forall i\in[1,n],0\le a_i<2^{30}$。
• 对于第一种操作，$1\le l\le r\le n$。
• 对于第二种操作，$1\le pos\le n$。

时间限制：3s。
空间限制：512MB。
::::: :::::info[闲话] KSCD 太巨了！
本题解有借鉴其题解相关内容。
::::: 通过观察数据范围，是 $10^5$ 量级的，然后开了 3s，猜测是根号复杂度带个 $\log$，同时莫队没有什么好突破，所以开始想分块。
同时如果对序列分块的话可能会有多次第一种操作导致影响力超过 $\Theta(1)$ 个块，所以考虑同时对序列和操作分块。
根据上述，我们设阈值为 $B$，对序列每 $B$ 个分一块，当第一次操作数达到 $B$ 时分一块，这样保证了影响力只会在相邻两个块间产生，那么我们做的时候就会简单一点。
现在我们考虑如何快速计算它们多次异或后的值，容易发现若进行了 $d$ 次操作，那么 $a'j$（多次操作前的 $a_j$）会贡献到 $a_i$ 这个地方 $\dbinom{d}{i-j}$ 次，现在需要判断这个值的奇偶性。
:::::success[引理]{open} 当且仅当二进制下 $y\subseteq x$ 时，$\dbinom{x}{y}$ 为奇数。
::::: :::::success[证明] 由 Lucas 定理：
$$\binom{x}{y}\equiv\binom{\lfloor\frac{x}{p}\rfloor}{\lfloor\frac{y}{p}\rfloor}\binom{x\bmod p}{y\bmod p}\pmod p$$ 其中 $p$ 是质数。
当 $p=2$ 时，我们得到：
$$\binom{x}{y}\equiv\prod{i=0}\binom{x_i}{y_i}\pmod 2$$ 其中 $x_i,y_i$ 分别代表 $x$ 和 $y$ 在二进制下第 $i$ 位的值。
注意到 $\dbinom{0}{0}=\dbinom{1}{0}=\dbinom{1}{1}=1$，只有 $\dbinom{0}{1}=0$，所以最终容易得到原引理。
证毕。
::::: 所以通过上面的引理我们得到：
$$a_i=\bigoplus_{i-j\subseteq d}a'_j$$ 这个式子可以使用 SOS DP 进行计算。
那么计算后有什么用呢？
具体地，我们对于相邻两个块，当这个操作是第一种操作且操作完全覆盖这两个块的时候我们令 $d\leftarrow d+1$，否则我们通过 SOS DP 直接清空标记然后对块内的数暴力进行操作即可。对于查询我们可以直接枚举子集计算。
这样复杂度是否正确？
对于每个第一种操作，容易发现被暴力计算的块最多只有 $4$ 个，所以暴力计算这部分的复杂度是 $\Theta(qB)$，同时在清空标记时会有 $\Theta(qB\log B)$ 的复杂度，查询时枚举子集会有 $\Theta(qB)$ 的复杂度，同时每个操作块结束时需要下放标记，会有 $\Theta(\dfrac{nq\log B}{B})$，所以总复杂度是 $\Theta(\dfrac{nq\log B}{B}+qB\log B)$，取 $B=\sqrt n$ 可得到 $\Theta(q\sqrt n\log n)$ 的复杂度。
时间复杂度为 $\Theta(q\sqrt n\log n)$，空间复杂度为 $\Theta(n+q)$。

code

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

:::::info[题目基本信息] 考察：构造，Ad-hoc，数位 DP，二分，倍增（无评分）。
题目简介：
一个网格图，原来上面有一个黑点 $(X,Y)$，然后你进行了下面的操作若干次：

• 选定 $x,y$，让 $(x,y),(x,y+1),(x+1,y)$ 中黑点变成白点，白点变成黑点。

最终有 $n$ 个黑点，以 $\{x_n\},\{y_n\}$ 的形式给出，求最开始的 $X,Y$。
数据范围：

• $1\le n\le 10^4$。
• $\forall i\in[1,n],|x_i|,|y_i|\le 10^{17}$。
• 保证有唯一解。

时间限制：4s。
空间限制：1G。
::::: :::::info[闲话] 这题是人能想到的？？？
没有人类了。
可以数数本篇文章有多少“注意到”。
::::: 注意到这个题没有像 CF2096D 那样优美的性质，所以这个题直接做超级难做，所以我们考虑转到一条直线上，就取 $Y=-10^{17}$ 吧。
注意到我们将这些点通过操作转化到 $Y=-10^{17}$ 这条线上来，具体地，若黑点为 $(0,0)$，那么令 $x=0,y=-1$，让 $(0,0)$ 变为白点，$(0,-1)$ 和 $(1,-1)$ 变为黑点。
这时我们注意到一个点被贡献奇数次才能真正被贡献，所以若 $(X,Y)$ 会被贡献成黑点，那么 $\dbinom{y_i-Y}{X-x_i}\equiv 1\pmod 2$，通过这里提到的引理可以得到 $X-x_i\subseteq y_i-Y$（二进制意义下，下同）。
注意到这一些黑点所贡献在这条直线上的黑点与原点所贡献的相同，所以我们找到这些黑点中的最左点和最右点就可以确定原点坐标了。
这样时间复杂度为 $\Theta(nV)$，显然过不去。
注意到我们并不需要找到所有贡献到这条直线上的黑点，找到最左点和最右点就足够了，所以我们考虑如何找到这两点。
注意到最左点的 $X_l-x_i=0$，最右点的 $X_r-x_i=y_i-Y$，其余黑点的 $X-x_i\subseteq y_i-Y$，所以我们得到 $X_l-x_i\subseteq X-x_i\subseteq X_r-x_i$，所以得到一个黑点后我们可以倍增求出最左点和最右点。
现在我们只需要得到一个落在直线上的黑点。
观察翻转的点注意到 $(x,y),(x,y+1),(x+1,y)$ 这些点的 $(x-y)\bmod 3$ 都是不同的，同时由于最开始只有一个点，所以必定有一个 $(x-y)\bmod 3$ 满足点数是奇数。
这有什么用呢？
注意到一段区间内点数的奇偶性是好算的，直接数位 DP 即可，所以我们考虑二分。
具体地，定出一个足够大的区间（列不等式算一算可以得到是 $[-V,3V]$），然后选中点判断两边的奇偶性，由于总点数是奇数所以必定有一边是奇数，然后就可以找出一个黑点了。
然后就做完了。
时间复杂度为 $\Theta(n\log^2 V)$，空间复杂度为 $\Theta(n+\log V)$。

code

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

:::::info[题目基本信息] 考察：倍增（省选/NOI-）。
题目简介：
你有 $n$ 个点，它们有点权，初始时它们间没有连边。
你需要进行 $m$ 次操作或查询：

• 操作：给两个不联通的点连边。
• 查询：询问两个连通的点间的路径的点权的最大子段和。

数据范围：

• $1\le n,m\le 3\times 10^6$。
• $-2^{31}\le a_i<2^{31}$。
• 数据强制在线。

时间限制：4s。
空间限制：512MB。
::::: 斜二进制倍增模板题（出题人题解）。
先引入斜二进制是什么。
:::::success[斜二进制] 斜二进制是第 $i$ 位表示的数是 $2^i-1$ 的一种进制（当然了尽可能用高位表示）。
容易发现一些性质：

• 每一位只可能出现 $0,1$ 或 $2$。
• 最多出现 $1$ 个 $2$。
• 若出现了 $2$，那么比 $2$ 所在位低的位都为 $0$。

设函数 $\text{skewlowbit}(x)$ 表示 $x$ 的最低的不为 $0$ 的位。
::::: 下面引入斜二进制倍增：
:::::success[斜二进制倍增] 定义一棵树是通过线段树偏移得到的，每个点都只作为一个区间的右端点，类似 BIT，每个点的区间为 $[x-\text{skewlowbit}(x)+1,x]$。
令 $lb_x=x-\text{skewlowbit}(x)$，这样方便我们跳区间，这样我们就可以倍增了。
类似 BIT 一样倍增即可。
::::: 在这个题中，斜二进制倍增要上树，每次新增点的时候选择较小的一个子树进行重构，时间复杂度是启发式合并的 $\Theta(n\log n)$。
讲的好像有点草率了。细节见代码吧。

时间复杂度为 $\Theta(n\log n)$。

code

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

:::::info[题目基本信息] 考察：贪心（$2858$）。
题目简介：
$t$ 组数据，每组数据给你一棵 $n+1$ 个点的有根树，根为 $0$，有一个关键点位于这棵树的任意非根节点，给定 $\{a_n\}$，表示 $\forall i\in[1,n]$，$i$ 点为关键点的概率为 $\dfrac{a_i}{\sum_{j=1}^na_j}$，定义一次操作为：

• 选择一个已被操作的点的儿子，对其操作。

初始时 $0$ 点已被操作，问操作次数的期望值的最小值是多少。
数据范围：

• $1\le t,n,\sum n\le 2\times 10^5$
• $\forall i\in[1,n],a_i\ge 1$
• $\sum_{i=1}^na_i\le 10^8$ ::::: 注意到这个题我们不能直接贪心选更优的点，因为更劣的点下可能有特别优的点，但是我们注意到这时选完这个劣点下一步肯定会直接选这个优点，这时我们就可以直接合并这两个点。
  现在我们要对“优”进行定义。
  我们一开始每个点的权值不妨直接设为 $a_i$，最后的时候再除以一个 $\displaystyle\sum_{i=1}^na_i$ 即可，那么合并后的点的权值是什么呢？
  这时，这个大点会对操作次数贡献 $2$，那么我们不妨考虑邻项交换法，令 $x$ 点的实际点数为 $b_x$，实际点的编号构成序列 $\{id_{x,b_x}\}$，对 $y$ 点做相同的定义。
  这时我们要求 $x$ 点在前，那么我们得到： $$(\sum_{i=1}^{b_x}ia_{id_{x,i}})+(\sum_{i=1}^{b_y}(i+b_x)a_{id_{y,i}})<(\sum_{i=1}^{b_y}ia_{id_{y,i}})+(\sum_{i=1}^{b_x}(i+b_y)a_{id_{x,i}})$$ 解得：$\dfrac{\sum_{i=1}^{b_x}a_{id_{x,i}}}{b_x}>\dfrac{\sum_{i=1}^{b_y}a_{id_{y,i}}}{b_y}$。
  这样我们就容易得到任意点的权值了。
  后面就可以直接用堆和并查集维护了，细节还是见代码。
  code