NOI 2025 即将来临，Public Round #16（supported by 云斗学院） 将在 2025 年 7 月 9 日至 2025 年 7 月 11 日举行，您可以在我们提供的若干时间窗口中选择一个参加比赛。
时间窗口列表：TBD
比赛将进行 5 小时，共 3 道题，IOI 赛制。
本次比赛的题目难度约为 NOI 难度，方便选手调整状态，所有题目都有部分分。
本次模拟赛的组题人为 @znstz，搬题人为 @Lynkcat @YunQian @znstz，验题人为 TBD。
赛后会公开原题链接和题解链接。
特别提醒：本次比赛的题目均为原题，但为了比赛的公平性，请勿在比赛时尝试查找原题地址。如不幸见过原题，请向管理员报告。
广告：云斗学院公益活动组 火热招人中！有意者请联系 znstz (qq: 1375455718)
UPD：原题：
搬题人：
验题人：
原题：
你可以在原题中找到非中文的题解，中文题解会稍后发布。
这是我第一次给 pjudge 搬题，不足知处请多多包涵。
你可以在本帖中尽情开喷，我会在下一场 pnr 中改进。
令操作结束后序列是 $y_1,y_2,\cdots,y_n$，容易发现，把 $x,y$ 分别排序，将 $x_1$ 变为 $y_1$，将 $x_2$ 变为 $y_2$ ……，是最优的。
于是问题变成了，把 $x_i$ 升序排列后，要求对于所有 $i(2 \le i \le n),x_i-x_{i-1} \ge d$，求最少操作次数。
考虑其差分序列，直接套用 UOJ-雪灾与外卖 的模拟费用流算法，能得 $70$ 分。
再次转化，将 $x_i$ 减去 $(i-1)d$，问题就变成了让 $x_i$ 不降，求最少操作次数，这个能直接做到 $O(n \log n)$。
先拆一下贡献，对于每条边，将它的经过次数加到答案里，最后答案加上 $2(n-1)$，就是真正的答案。
考虑把 $u$ 挂在 $v$ 上的过程，令 $S$ 表示 $u$ 所在连通块的点集，则 find(u) 到 find(v) 这条边的经过次数为：$-2(|S|-1)-1+\sum_{x \in S} deg(x)$。令这一坨式子为一个连通块的权值，显然，我们应该把 $u,v$ 所在连通块中，权值较大的挂在权值较小的上面。
继续观察，假设 $u$ 所在连通块的权值比 $v$ 大，那么把 $v$ 里面的点一个一个挂到 $u$ 上一定是更优的。
枚举起点，将树定根在起点，问题变成了，每个点有一个权值，将 $0,1, \cdots, n-1$ 放到每个点上，要求父亲的数大于儿子，最大化每个点上权值乘上数的和。这是经典的问题，每次取权值最大的，它上面的数一定是父亲的 $-1$，将它和父亲合并就行，新权值设为连通块内的平均数。
复杂度 $O(n^2 \log n)$。
考虑最朴素的 dp：$dp(i)$ 表示前 $i$ 个数的最大价值，转移 $dp(i)+mex(i+1,j) \cdot sum(i+1,j) \rightarrow dp(j)(j-i \le k)$。
从 $1$ 到 $n$ 依次计算 dp 值，令当前算到的位置为 $i$，先维护每个位置到 $i$ 这一段的 $mex$，直接开珂朵莉树维护其连续段，能分析出总共只有 $O(n)$ 次连续段的变化。
转移考虑根号重构，令 $B=\lfloor\sqrt{n} \rfloor$，若 $i \bmod B=0$，则重构 $[i-k+B,i]$ 这一段的贡献，转移的时候对于散块暴力算，复杂度 $O(n \sqrt {n})$，实现起来很多细节。
据说存在 polylog 做法，敬请期待官方题解（。
考虑 dp，$dp(i)$ 表示，考虑前 $i$ 个数，$a_i$ 选了，的最大权值，转移枚举 $j(j \gt i)$。
优化转移，如果 $i,j$ 之间有一个 $k(i \lt k \lt j)$，且 $a_i \&a_k$ 的最高位和 $a_i \& a_j$ 相同，那么选上 $a_k$ 一定更优（$2 \cdot 2^{a_i \& a_j 的最高位} \gt a_i \& a_j$，枚举 $a_i \& a_j$ 的最高位，找到前面第一个这一位是 $1$ 的数转移就行，复杂度 $O(n \log A)$。
赛时有人挂，原因是没考虑 $a_i \& a_j=0$ 的情况，hack：$a=\{4,4,2,2\}$。
fun fact: pb 认为这个题是一眼题。
最直观的一个结论：除了最后一条命，都只做”深入思考“操作。
考虑二分，二分复活次数 $d$，计算经过 $d$ 条命的“深入思考”后，最少在下一条命中需要多少时间能完成任务。最后一条命，每个任务需要的时间是：
考虑这样一个贪心策略，每次选择能减少时间最多的进行“深入思考”，原因是代价关于 $t$ 是凸的。
假设任务 $i$ 被想了 $t$ 次，则需要满足：$t \le d, \sum t \le c \cdot d$。
但是 $c,d$ 可能会特别大，观察到对于 $t \ge 2d$ 的任务，进行一次“深入思考”会产生 $d$ 的时间减少。将所有任务按 $d$ 从大到小排序，尽可能操作直到 $t \lt 2d$ 或操作次数用完。之后每个任务至多被操作两次，把这两次的时间减少量搞出来再贪一遍就行。
复杂度 $O(n \log n \log A)$。
fun fact: 我认为这个题是一眼题。
考虑点双缩树，$x$ 走到 $z$ 必须经过 $y$，当且仅当 $y$ 是割点，且 $x$ 和 $z$ 在 $y$ 的不同子树中。
分 $y$ 是否在 $x$ 子树两种情况讨论，每种情况都分别令 $O(1)$ 个 dfs 序区间内的点不合法。
复杂度 $O(n \log n)$，有一种情况需要求 $x$ 的 $dep_y-dep_x-1$ 级祖先，
fun fact：这个题成为了签到题，前三题通过 $18,12,22$ 位选手。
讲下我的做法，实测 $118$ 次操作，能过原题。
考虑只有 $0,1$，将连续段放在一起考虑，序列形如 $10101010 \cdots$，考虑一次操作让 $0$ 连续段个数减半，分段类似 $1|0|10|1|0|10\cdots$，最后可能会搞出 $101$ 的形式，再来一次操作 $1|01$，就能排好序了。
考虑分治，将 $\le n/2$ 的看成 $0$，$\gt n/2$ 的看成 $1$，进行只有 $0,1$ 的算法，然后往两边递归，同一层可以放在一起处理，如果最后顺序不对再整体 reverse 一下就行。操作次数大概是 $0.5 \cdot\log^2 n$
先考虑循环节，等概率选取一个长度为 $n$ 循环节为 $d$ 的字符串，考察最小表示在 $f$ 处的概率，若 $f \le d$，则概率为 $d^{-1}$，否则为 $0$。
先计算循环节为 $d$ 的字符串个数 $cnt(d)$，这个可以用莫反求，$cnt(d)=\sum_{c|d} \mu(c)26^{d/c}$。
然后问题就变成了，每次询问两个数 $m,n$，求等概率选择一个长度为 $n$ 的字符串和一个长度为 $m$ 的字符串，最小表示位置相同的概率。枚举位置 $f$，概率是 $(\sum_{d|n, f \le d}cnt(d)d^{-1}26^{-n}) \cdot (\sum_{d|m, f \le d}cnt(d)d^{-1}26^{-m})$。
观察到两部分都可以被分为至多 $\sqrt{A}$ 段相等的连续段，$A$ 是值域，复杂度 $O(n \sqrt{A})$。
部分分在暗示做法。
最关键的一个性质：考虑第 $i$ 个数 $h_i$ 在最后被换到了 $p_i$ 的位置，那么最终状态下，第 $p_i$ 个数是 $(-1)^{i-p_i}h_i$，且操作次数是 $p_i$ 的逆序对数。
先考虑 $|h_i| \neq |h_j|$ 的部分分，按绝对值从大往小枚举，当前枚举到的数，要么丢到末尾且符号为正，要么丢到开头且符号为负。令 $dp(i,0/1)$ 表示，已经枚举了前 $i$ 个数，开头的数模 $2$ 是什么。转移只需要用 BIT 优化一下计算逆序对。
再考虑 $|h_i| \le 1$，由于符号翻转很烦，需要一点点的转化去掉它。令初始状态为 $a_1,\cdots,a_n$，目标状态为 $b_1,\cdots,b_n$，对于所有奇数（偶数也行）的 $i$，将 $a_i,b_i$ 取相反数，操作就变成了“交换相邻数，没有符号翻转”（理由：转化前后对于符号的要求均为，若 $|i-p_i|$ 为偶数，需要 $a_i,b_{p_i}$ 符号相同；若 $|i-p_i|$ 为奇数，需要 $a_i,b_{p_i}$ 符号相反）。
在转化后的问题上，需要对于一个 $-1,0,1$ 的序列求出，变成某个序列（中间一段为 $0$，左右两段 $+1,-1$ 交替排列）所需要的最小交换次数。
先做单组询问：给最终状态用 $[1,n]$ 顺次标号，给初始状态中的标号满足：对于所有 $x,y$，第 $x$ 个数 $y$ 在两个状态中的标号相同。操作次数就是初始状态标号的逆序对。
对于多组询问需要一点分讨，一个稍微简单的做法是，分 $0$ 左边的数有奇数还是偶数两种情况。对于同种情况，将 $0$ 的区间往右移动两步后，标号序列的变化也仅仅是将两个数的标号移到中间一段 $0$ 的前面，很容易用 BIT 计算逆序对的变化量。
考虑满分做法：$dp$ 状态一样，按绝对值 $x$ 从大到小枚举的时候，将 $+x$ 看成 $+1$，$-x$ 看成 $-1$，绝对值小于 $x$ 的看成 $0$。有时候 $0$ 会很多，但是计算逆序对的时候只需要分别计算：$(-1,0),(1,0),(-1,1)$ 之间的贡献，额外用 BIT 维护 $0$ 的位置即可。
复杂度 $O(n \log n)$。
不会，咕
