T1 空泣

原题 P11663，是小 X 推荐的，使用了小 S 帮忙搞的官方数据。

比较容易，也没卡 $\mathcal O(n\log n)$ 做法，难度不超过绿。

另外子任务 $3,4$ 没想到简便做法，有的话欢迎分享。

Sol.1

枚举答案，再枚举起始位置，每次 $\mathcal O(n)$ 扫一遍判合法。复杂度 $\mathcal O(n^2r)$，其中 $r$ 为答案，期望得分 $10$。

Sol.2

$x$ 合法必有 $x+1$ 也合法，于是答案可二分，同样枚举起始位置判断即可。复杂度 $\mathcal O(n^2\log V)$，期望得分 $30$。

Sol.3

枚举起始位置后快速算答案，以从 $1$ 开始为例，答案为 $\max_{i=1}^n a_i-s_{i-1}$，其中 $s$ 为 $b$ 的前缀和。对所有起点的答案求最值即可，复杂度 $\mathcal O(n^2)$，期望得分 $30$。

Sol.4

将 $a,b$ 重复一遍实现断环为链，在长为 $2n$ 的数组上对 $b$ 做前缀和得到 $s$。之后对 $p\in[1,n]$ 分别求区间 $[p,p+n-1]$ 的答案，即 $\max_{i=p}^{p+n-1} a_i-(s_{i-1}-s_{p-1})$，求 $a_i-s_{i-1}$ 的区间最小值即可。区间左右端点均递增，可单调队列 $\mathcal O(n)$ 解决，期望得分 $100$，当然也可以前后缀分别求。另外 ST 表或线段树的 $\mathcal O(n\log n)$，以及二分的 $\mathcal O(n\log V)$ 都能过。

T2 诗空茫

小 X 供题的加强，他给的是 $n\le 5000,m=10^7+7$，也就是本题的 $80$。

$80$ 大概是绿题难度，后面 $20$ 非常难推，推导难度可能有紫到黑，个人只会已知结论倒过来证明，如果会打表 + 注意力够强应该也能做出来。

不存在长为 $3$ 的上升子序列即最长上升子序列长度不超过 $2$，用 $n!$ 减去这样的排列数量即为答案。

Sol.1

暴力枚举全排列或状压 DP，复杂度 $\mathcal O(n!\text{poly}(n))$ 或 $\mathcal O(2^n\text{poly}(n))$，期望得分 $[5,15]$。

Sol.2

考虑最长上升子序列的求解过程，即从左往右扫，实时维护当前长为 $i$ 的上升子序列结尾最小值 $g_i$。由于长度不超过 $2$，且显然 $g_1=1$，状态为 $f_{i,x}$ 表示长为 $i$ 的排列中 $g_2=x$ 的数量，边界为 $f_{2,2}=1$。

状态中 $x$ 即前 $i$ 个数中当前 $g_2$ 的相对排名，于是枚举 $p_{i+1}$ 在前 $(i+1)$ 个数中的相对排名即可转移。注意还需考虑从降序排列转移来的情况，最后也要把降序排列减去。复杂度 $\mathcal O(n^3)$，期望得分 $40$。

Sol.3

另一种思路是从小往大填，此时新加的值最大，因此不能放在当前长为 $2$ 的上升子序列（顺序对）之后，于是状态内需记录最靠前的顺序对结尾。设 $f_{i,j}$ 表示填了前 $i$ 小值后最靠前的顺序对结尾为 $j$ 的排列数量，边界为 $f_{2,2}=1$，可枚举 $(i+1)$ 的相对位置转移，细节同上。复杂度 $\mathcal O(n^3)$，期望得分 $40$。

感性理解可以发现上面两种做法基本相同，其实写出来一模一样，本质是在 $(i,p_i)$ 的二维平面内扫描一维，并记录另一维的信息以便转移。

$m=998244353$ 是给 $\mathcal O(n^3)$ 做法打表的，期望得分 $50$。这也是为什么只有 $n$ 的计数题要输入模数。

Sol.4

上面的 $\mathcal O(n^3)$ 做法非常容易后缀和优化，于是就 $\mathcal O(n^2)$ 了，期望得分 $80$。

Sol.5

给出结论：长为 $n$ 且最长上升子序列长度不超过 $2$ 的排列数量为卡特兰数第 $n$ 项。

证明考虑构造双射，将 $n$ 个点 $(i,p_i)$ 画到平面上，找到 $p_i$ 后缀最大值位置集合。以这些位置为拐点，画出从 $(n,0)$ 到 $(0,n)$ 的折线。由于长为 $i$ 的后缀最大值不低于 $i$，折线除端点外均在直线 $x+y=n$ 上方。于是从后往前，每个前缀中向上次数不低于向左次数，作为两种括号即为合法括号序列，合法折线数量即卡特兰数。

显然任意排列可映射到唯一合法折线，下面证明任意合法折线可映射到唯一合法（最长上升子序列长度不超过 $2$ ）排列。对于合法折线，可通过拐点还原出所有后缀最大值及位置。要构成合法排列，剩余值必须按降序依次填入空位，否则存在非后缀最大值位置 $i\lt j,p_i\lt p_j$，此时找到某个后缀最大值位置 $k\gt j$，长为 $3$ 的上升子序列 $i,j,k$ 会使排列非法。于是结论得证，合法排列与合法折线形成双射，两者数量相等，均为卡特兰数。

于是求卡特兰数第 $n$ 项 $\frac {2n\choose n}{n+1}$，在 $m$ 为质数时可通过阶乘及逆元求，复杂度 $\mathcal O(n)$。期望得分 $20$，拼上 Sol.4 期望得分 $90$。

Sol.6

$m$ 为合数时有的数不存在乘法逆元，无法实现除法。将式子拆组合数约分得到 $\frac{\prod_{i=n+2}^{2n}i}{\prod_{i=1}^ni}$，可求出该值中每个质因子的次数，最后快速幂求出答案。线性筛出 $2n$ 内所有质数及每个数的最小质因子，之后依次分解质因数加入，用桶维护当前次数即可。复杂度为分解质因数的 $\mathcal O(n\log n)$，期望得分 $100$。最后的快速幂其实是 $\mathcal O(n)$ 的，因为质数只有 $\mathcal O(\frac {n}{\log n})$ 个。

T3 血路

SDSC2025 D3T3 By do_while_true，原题。

数据自造，强度未知，但已经对着小 S 的错解尽可能卡了。

最优解中所有区间必然首尾相接，否则可调整消掉中间的空位。

另外可先找到所有区间的交点 $x$，并通过整体平移将交点变为 $0$，方便之后讨论。这样就变成原题了。

Sol.1

根据上述结论可以写一些暴力，期望得分 $[5,30]$。

Sol.2

观察最优解结构，设完全在 $0$ 左侧的区间有 $x$ 个，完全在 $0$ 右侧的区间有 $y$ 个。只要 $x\ne y$，就能将解整体向 $x,y$ 中较小的一侧平移，这样这些区间贡献严格减少，包含 $0$ 的区间只可能贡献 $1,-1$，总体代价必然不增。

若 $n$ 为偶数，根据上述调整最优解必然存在一个区间端点为 $0$，且 $0$ 将所有区间分成数量相同的两部分，这可以 DP 解决。令左右两侧区间集合从远到近分别为 $p,q$，零下标下答案为 $\sum_{i=0}^{\left|p\right|-1} (r_{p_i}+\sum_{j=i+1}^{\left|p\right|-1} len_{p_j})+\sum_{i=0}^{\left|q\right|-1}(-l_{q_i}+\sum_{j=i+1}^{\left|q\right|-1}len_{q_j})$，其中 $len_i=r_i-l_i$，含义即所有区间需要移动的次数和。

将 $len$ 项拆贡献避免对 $j$ 的枚举，可得 $\sum_{i=0}^{\left|p\right|-1} (r_{p_i}+ilen_{p_i})+\sum_{i=0}^{\left|q\right|-1}(-l_{q_i}+ilen_{q_i})$，最小化时显然小的 $i$ 应对应大的 $len$，即 $p,q$ 分别按 $len$ 降序排序最优。于是初始对所有区间按 $len$ 排序，之后 DP 设 $f_{i,j}$ 表示前 $i$ 个区间中 $j$ 个在 $0$ 左侧的最小贡献和，即可 $\mathcal O(n^2)$ 解决偶数情况，期望得分 $50$。

Sol.3

对于 $n$ 为奇数的情况，最终两侧区间数量必然相等。此时在中间区间包含 $0$ 的前提下左右平移时，两侧区间贡献不变，因此中间区间位于初始位置最优。令中间区间为 $t$，$p,q$ 含义同上，答案为$\sum_{i=0}^{\left|p\right|-1} (r_{p_i}+\sum_{j=i+1}^{\left|p\right|-1} len_{p_j})+\sum_{i=0}^{\left|q\right|-1}(-l_{q_i}+\sum_{j=i+1}^{\left|q\right|-1}len_{q_j})-\left|p\right|l_t+\left|q\right|r_t$，即两侧区间初始要移到 $t$ 两侧。枚举中间区间 $t$ 后可以同样 DP，总复杂度 $\mathcal O(n^3)$，期望得分 $35$，拼上 Sol.2 期望得分 $85$。

Sol.4

事实上由于 $\left|p\right|=\left|q\right|=\frac{n-1}2$，式子最后两项必为 $\frac{n-1}2len_t$。于是不需要枚举中间区间，直接设 $f_{i,j,0/1}$ 表示前 $i$ 个区间中 $j$ 个在 $0$ 左侧，是否已有中间区间的最小贡献和，过程中确定即可做到 $\mathcal O(n^2)$。另外部分转移与偶数情况相同，偶数时不选中间区间即可，可以写在一起。期望得分 $100$。

T4 欲泪海

SDSC2025 D1T4 By yixiuge777，原题 CF1540D，其实也没有特别难。

另外特殊性质 B 没想到简便做法，有的话欢迎分享。

Sol.1

每次询问枚举全排列，复杂度 $\mathcal O(qn!\text{poly}(n))$，期望得分 $5$。

Sol.2

注意到 $b_i$ 确定了 $p_i$ 在前 $i$ 个数中的相对排名，于是从左往右扫，维护当前前缀内所有数的大小关系，每次将 $i$ 插入到第 $(b_i+1) $ 大的位置；也可以从右往左扫，每次将 $p_i$ 确定为当前未使用过的第 $(b_i+1)$ 大值。这样可以求出整个排列，暴力做总复杂度 $\mathcal O(qn^2)$，A 性质下 $\mathcal O(n^2+q)$，期望得分 $15$。

通过该做法可以证明 $b$ 数组对应唯一的合法排列 $p$，两者能形成双射，题面里的最小值是诈骗。

Sol.3

数据结构加速 Sol.2 的过程，比较容易的是倒着确定值，用权值线段树 / 树状数组上二分即可。总复杂度 $\mathcal O(qn\log n)$，A 性质下 $\mathcal O(n\log n)$，期望得分 $40$。

Sol.4

注意到只询问单个位置，求出整个排列有点浪费。只关注 $p_i$ 的值，从前 $i$ 个数开始不断向后扩展，维护当前 $p_i$ 的相对排名 $x$，初始为 $b_i+1$。加入位置 $j$ 时，若 $b_j\ge x$ 则 $x$ 不变，否则 $x$ 加一，这样最终得到的 $x$ 即为答案。总复杂度 $\mathcal O(nq)$，期望得分 $45$，拼上 Sol.3 做 A 性质期望得分 $55$。

Sol.5

数据结构加速 Sol.4 的过程。注意到 $j$ 位置会将 $x\gt b_j$ 的 $x$ 加一，增加量是分段一次函数。线段树维护区间一次函数复合，则长为 $len$ 的区间一次函数至多有 $(len+1)$ 段，且必然单调不降。将信息压到段数级别，维护 $a_i$ 表示函数中加 $i$ 的最小 $x$ 值，$a$ 是长为 $\mathcal O(len)$ 的单调不降数组。查询时在 $a$ 上二分即可。

考虑将 $f,g$ 合并得到 $h$，根据定义有 $h_i=\min_{j=0}^{i}(\max(f_j,g_{i-j}-j))$。有结论：令 $h_i$ 取最小值的 $j$ 为 $t_i$，则 $t$ 是单调不降的，即 $t_i\le t_{i+1}$。证明考虑首先 $h_i$ 不降，因为 $f_j$ 不变且 $g_{i-j}$ 随 $i$ 增大而增大。之后求 $h_{i+1}$ 可从 $x=h_i$ 开始枚举 $x$ 并检查是否合法，方式为取 $f_j\le x$ 的最大 $j$，看 $\max(f_j,g_{i-j}-j)$ 是否不超过 $x$。在该过程中用于检查的 $j$ 不会低于 $t_i$，于是 $t_{i+1}\ge t_i$。

有了上述结论，用指针维护当前最优的 $j$，可 $\mathcal O(len)$ 合并出长为 $len$ 的数组 $h$。于是线段树维护区间信息，单点修改时从叶子修改到根，单次复杂度 $\mathcal O(n)$。查询时依次在对应的 $\mathcal O(\log n)$ 个节点上二分，单次复杂度 $\mathcal O(\log ^2n)$。总复杂度 $\mathcal O(qn)$，A 性质下 $\mathcal O(n\log n+q\log^2 n)$，期望得分 $55$。

另外其实有更强结论：$t_{i+1}\in\{t_i,t_i+1\}$，证明需观察 $h_i$ 的结构，由于最小值必取在单增的 $f_j$ 和单减的 $g_{i-j}-j$ 交点处，讨论交点两侧大小关系即可证明。用该结论会略微降低实现难度和常数，不太重要。

Sol.6

对于这种修改查询复杂度不平衡的情况，可以使用分块平衡。具体地，每 $B$ 个位置分一块，每块开线段树维护整块函数信息，单点修改复杂度降到 $\mathcal O(B)$；查询时暴力跳所在块内元素，再依次在后面块上线段树根节点二分，查询复杂度为 $\mathcal O(B+\frac{n}B\log B)$，平衡取 $B=\sqrt{n\log n}$ 即有复杂度 $\mathcal O(q\sqrt{n\log n})$，期望得分 $100$。实际上由于线段树的大常数和 upper_bound 的小常数，$B$ 取小一点会跑得更快。

另外使用双指针或分散层叠似乎可以做到单根号，不过常数应该不小，意义不大。

后记

感谢推荐 / 提供了前两题的小 X，进行了部分验题的小 S，以及一起讨论 T2 证明的小 W、小 C 和小 D。

MOCKER44. 好听。SSP 是其外号 烧诗P 的缩写，并非费用流算法。SSP Round 1 可在此处查看。

最后祝大家春节快乐！之后都能 rp++！

爆竹鸣响长夜未已

飞鸟衔新叶回巢

归乡自天涯海角

山间的小路它也此刻往来热闹

齐思量出游相邀

共祝来年节节高

结彩串巷共迎灯宵

——MOCKER44. / 洛天依《游春》