本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-26 09:30:51
09.25
T1 被前导零挂到 $30$ 了，其他打得还行。
T4 的 DP 只保留有效状态，值得学习。T5 的数据结构可以练习码力，已严肃练习。
T4 学术竞赛
题意
有 $n$ 名参赛者和 $m$ 道题，每人每题的得分均在 $[0,k]$ 内。给出所有得分情况 $a_{i,j}$，问最少保留多少个 $a_{i,j}$ 能唯一确定出原来的排名，分数相同的按编号从小到大排序。$n\le 2\times 10^4,m,k\le 100$。
题解
先排出目标排名 $p$，之后设 $f_{i,j}$ 表示考虑了排名前 $i$ 的所有人，且 $p_i$ 的分数下界 $l_{p_i}=j$ 时，最多能删掉多少个数。状态数是 $O(nmk)$ 的，转移时考虑枚举当前的左端点 $l$ 和删的个数 $c$，若 $p_i$ 删掉 $c$ 个数后和可为 $l$，则可转移 $f_{i,l}\leftarrow\max_{j=l+ck+[p_{i-1}>p_i]}^{mk} f_{i-1,j}$，可预处理后缀最大值，转移复杂度为 $O(nm^2k)$。转移前还需求出 $g_{c,l}$ 表示能否删掉 $c$ 个数后恰为 $l$，这可以使用背包解决，总复杂度 $O(nm^3k)$ 或 $O(\frac{nm^3k}w)$，难以通过。
接着发掘本题的性质，发现 $l_i\le s_i\le r_i$，即删数后的取值区间一定包含原来的和。那么一定有 $s_{p_{i+1}}\le l_{p_i}\le s_{p_i}\le r_{p_i}\le s_{p_{i-1}}$，否则一定不满足限制。设 $t_i=s_{p_i}-s_{p_{i+1}}$，有 $l_{p_i}\in[s_{p_{i+1}},s_{p_i}],s_{p_i}-l_{p_i} \le t_i$。于是以 $t_i$ 为最大容量做背包，也只枚举 $t_i$ 种 $l$，后缀最大值也只取 $i-1$ 有意义的部分。这样单次背包复杂度为 $O(m^2 t_i)$，单次转移复杂度为 $O(mkt_i)$。由于 $\sum t_i=O(mk)$，总复杂度为 $O(m^3k+m^2k^2)$，可以通过。
原题
P13345。
T5 lunatic 难度佩洛洛斯拉
题意
有一个两维大小均为 $n$，初值均为 $0$ 的数组 $a$，先进行 $n$ 次矩形 checkmax，再求 $m$ 次矩形和，保证修改的 $xl=1$ 或 $xr=n$。$v\le n\le 10^6,m\le 5\times 10^5$，时间限制 $16$ 秒。
题解
考虑保证全部 $xl=1$ 怎么做，由于只有前缀操作，此时每一行元素均不降。因此从右往左扫描线，扫到修改右边界时区间 checkmax，查询差分成两个后缀，在对应时刻查询历史和。全部 $xr=n$ 的情况是类似的，此时每行元素不增。
两种都存在时，设 $A_{x,y},B_{x,y}$ 分别表示只考虑 $xl=1,xr=n$ 的操作时 $a_{x,y}$ 的最终值，则同一行内 $A$ 不降 $B$ 不增，$\max(A_{x,y},B_{x,y})$ 在一段前缀内取 $A$，剩下的后缀内取 $B$。设该位置为 $p_y$，若能求出所有 $p_y$ 的值，可以拆分成两半分别进行上一段的扫描线，需要额外维护 $v_y$ 表示目前第 $y$ 行是否贡献，初始 $v$ 全为 $0$，过程中加入 $v$ 单点赋值为 $1$ 的操作，查询同样是历史和。
考虑 $p_y$ 怎么求，从下向上扫描线，则需要支持 $A$ 前缀或 $B$ 后缀 checkmax，两种均需支持撤销，查询最后一个 $A_x\ge B_x$ 的位置 $p_y$。由于区间改的撤销是困难的，考虑转为单点改 $A',B'$，则 $A$ 为 $A'$ 的后缀 max，$B$ 为 $B'$ 的前缀 max，使用线段树维护 $A',B'$，并在上面二分求 $p_y$ 即可，过程中需要记录目前后面的 $\max A'$ 和前面的 $\max B'$，时间复杂度 $O(n\log n)$。
剩下的问题是左右两轮扫描线，需要维护初始全 $0$ 的序列 $t,v$，支持 $t$ 区间 checkmax，$v$ 单点赋值为 $1$，查询区间 $tv$ 历史和。使用吉司机线段树，只在 $mn\lt v\le mn'$ 时打标记修改，同时使用一次函数维护历史和。注意这里懒标记也需要用一次函数，维护最小值变化过程中的贡献。时间复杂度不会分析，不知道是 $O(n\log n)$ 还是 $O(n\log^2 n)$，反正不超过后者且能过。
09.27
这回 T1 没挂。T2 挂了，原因是 DP 上界没有对 $m$ 取 min，理论上能卡到很低分但还有 $80$。
T3 是神秘调整贪心题，不会做。T4 是神秘 Hall 定理 + 数据结构，太困难。已严肃学习。
T2 在空无一物的时光深处
题意
有一个长为 $m$ 的画板，可任取笔刷的初始位置 $p$，需要依次涂 $n$ 种颜色，每次可选择终点 $q$ 为 $p-c_i+1$ 或 $p+c_i-1$，要求 $1\le q\le m$。之后将该区间内均涂成 $i$ 并将 $p$ 赋值为 $q$。求最终颜色不同的画板种类数。$n,m\le 150$。
题解
注意到顺着考虑时很容易记重，即一种画板形态对应多种最终位置。因此倒着考虑每次涂色，这时只能涂之前没涂过的位置，因此设 $f_{i,l,r,0/1}$ 表示考虑了后 $i$ 次涂色，当前有颜色的区间为 $[l,r]$，且笔刷最终位于左 / 右端点的方案数。注意到只有 $n$ 一种颜色时还是会重，因此要枚举第二种颜色作为 DP 初始值。
转移时需要枚举下一次真正涂出颜色的操作 $j$，并要求 $(i,j)$ 内的移动可以限制在 $r-l+1$ 长度内，且最终停在某个位置，之后拓展出去若干格即可。在某长度内移动的限制可以使用背包，设 $g_{i,j,lim,k}$ 表示考虑 $[i,j]$ 内的操作，不能超出 $[0,lim]$，最终能否到达 $k$。转移是 $O(1)$ 的，因此背包复杂度为 $O(n^2m^2)$。
然而此时 DP 需要枚举 $i,j,l,r$，还要枚举新染出去的长度 $d$，复杂度为 $O(n^2m^3)$，无法通过。然而注意到长度 $r-l$ 相等的 $f_{i,l,r}$ 均相同，因此这两维可以压成 $len$ 一维，状态数变成 $f_{i,len,0,1}$ 的 $O(nm)$，总复杂度降为 $O(n^2m^2)$，可以通过。
T3 烟花
题意
有 $n$ 种烟花，第 $i$ 种有 $c_i$ 个且点燃成功率为 $p_i$。要求从中选出 $k$ 个依次点燃，最小化某一个点燃失败且上一个点燃成功的期望次数。多组数据，$T\le 10,n\le 10^5,k\le 10^9,\sum c\ge k$。
题解
感觉非常不可做，需要挖掘其性质。令选择的烟花编号为 $a_i$，烟花总数为 $m=\sum c$。先考虑确定了选出的 $k$ 个烟花后如何排列，从而最小化 $\sum_{i=1}^{k-1} p_{a_i}(1-p_{a_{i+1}})=\sum_{i=1}^{k-1} p_{a_i}-p_{a_i}p_{a_{i+1}}$。首先最大化后一项，根据排序不等式或调整法可知升序或降序时最大，又由于 $p_{a_k}$ 不贡献，整个序列不降时取到最小值。
此时可以先把 $n$ 种烟花按 $p$ 升序排序，然而还是不好做，需要更深入的性质。若有 $x<y<z$ 三个值，贡献为 $x+y-xy-yz=y(1-x-z)+x$，于是有 $x+z\ge 1$ 时 $y$ 越大越好，$x+z\lt 1$ 时 $y$ 越小越好，因此 $y$ 一定会取到原序列中 $x$ 后一个或 $z$ 前一个。
这可以说明选择大概是比较集中的，下面尝试证明选的是一个前缀加一个后缀。首先有 $p_1(1-p_{a_2})\le p_{a_1}(1-p_{a_2})$ 且 $p_{a_{k-1}}(1-p_m)\le p_{a_{k-1}}(1-p_{a_k})$，因此 $1$ 和 $m$ 必选。之后设目前选的最长前缀为 $l$，最长后缀直到 $m-r+1$，并试图将离二者最近的元素调整进来。
具体地，若将 $a_{l+1}$ 调整为 $l+1$，则变化量为 $p_l(1-p_{l+1})+p_{l+1}(1-p_{a_{l+2}})-p_l(1-p_{a_{l+1}})-p_{a_{l+1}}(1-p_{a_{l+2}})$，整理可得 $(p_{a_{l+1}}-p_{l+1})(p_l+p_{a_{l+2}}-1)$，在 $p_l+p_{a_{l+2}}\le 1$ 时调整不劣；同理可得将 $a_{k-r}$ 调整为 $m-r$ 的变化量为 $(p_{m-r}-p_{a_{k-r}})(1-p_r-p_{a_{k-r-1}})$，在 $p_{a_{k-r-1}}+p_r\ge 1$ 时调整不劣。
这时若 $p_l+p_r\le 1$，由于 $p_{a_{l+2}}\le p_r$，可将 $a_{l+1}$ 调整为 $l+1$；否则 $p_l+p_r\ge 1$，由于 $p_{a_{k-r-1}}\ge p_l$，可将 $a_{k-r}$ 调整为 $m-r$，这就证明了最终一定能调整成一段前缀加一段后缀。
这也引出了做法：维护目前的 $l$ 和 $r$，若 $p_l+p_r\le 1$ 则加入 $l+1$，否则加入 $m-r$，重复该过程直到选出 $k$ 个。由于同种烟花的 $p$ 相等，可令 $l,r$ 一直为某种的端点，每次将 $l,r$ 不变的一段全放进来，可以做到关于 $n$ 线性。时间复杂度 $O(n\log n)$，在初始按 $p$ 进行排序。
原题
P4110。
T4 归风
题意
定义序列 $b$ 权值为初始 $x=0$，每次操作可将 $x$ 增加 $1$，或让某个 $b_i$ 异或上 $x$，将 $b$ 全变为 $0$ 的最小操作次数即其权值。给出长为 $n$ 的序列 $a$，$q$ 次询问其 $[l,r]$ 区间内序列的权值。强制在线，$n,q\le 2\times 10^5,a_i\lt 2^{60}$。
题解
$x$ 的最终值是一个上界，可以任意使用不超过该值的数操作。先找出区间内 $1$ 的最高位 $2^p$，显然 $x\ge 2^p$，否则该位消不掉。之后所有不超过 $x$ 的数均可以一次消掉，其余数均需要两次消掉，答案为 $\min_{x\ge 2^p}(x+\sum_{i=l}^r[a_i\gt x]) +r-l+1$。将 $c$ 个 $a_i\gt2^p$ 的数和 $x$ 拿出来并减去 $2^p$，所求即 $\min(x+\sum_{i=1}^c[b_i\gt x])$，稍加转换即可得到 $c-\max(\sum_{i=1}^c[b_i\le x]-x)$，最终答案即 $2^p+r-l+1$ 加上这个值。
Hall 定理告诉我们，二分图最大匹配中左部失配点数为 $\max_S(\left|S\right|-\left|N(S)\right|)$。试图将上面的式子与其对应起来，则 $\left|N(S)\right|=x$，需要有 $x$ 个右部点，同时对应的左部点应该表示 $\sum_{i=1}^c[b_i\le x]$。考虑以每个 $b_i$ 为一个左部点，以每个整数值为一个右部点，左部 $b_i$ 向所有满足 $x\le b_i$ 的右部点 $x$ 连边，显然这是一个前缀。因此 $N(S)$ 也总是一个前缀，当其为 $[1,x]$ 时会选择所有 $b_i\le x$ 的 $b_i$，这是合法的最大 $S$，容易发现其他情况不会得到比原式更大的结果，因此这样构造是对的。
这样在该图上求出最大匹配数，即为所求的 $c-\max(\sum_{i=1}^c[b_i\le x]-x)$。由于左部点向右边前缀连边，以任意顺序枚举左部点并找最大右部点与其匹配是对的，不妨钦定顺序从右到左将 $[l,r]$ 内的点尽量匹配。对整个序列从左到右扫描，并实时维护 $[1,r]$ 从后往前依次匹配的结果。
由于后面的优先级更高，新加入 $r$ 时会强制匹配 $r$，这可能导致整个匹配不合法。仍然使用 Hall 定理，不合法也就是存在 $x$ 使得 $\sum_{i\in S}[b_i\le x]-x\gt0$。使用线段树维护每个 $x$ 的这个值，加入 $r$ 时对 $b_r$ 的后缀加 $1$，此时若存在 $x=1\gt0$，就找到最小的 $x$，再从 $x$ 前面找到编号最小的 $t$，将其从匹配中删去，从而保证 Hall 定理的条件仍然成立。容易发现某元素删去后一定不会再加回来，因此这是对的。
综上，线段树需要维护区间最大值及第一个最大值的位置，还要支持在每个点上维护一个集合，查询前缀集合内最小元素，这都是不难实现的。由于每个询问最高位 $2^p$ 唯一，且此时只关心 $(2^p,2^{p+1})$ 内的数，对所有这样的集合分别预处理该过程即可。由于区间无交，总复杂度是 $O(n\log n)$ 的。
此时得到了每个点在 $r\in[i,lim_i]$ 时在匹配中，同时还有 $l\le i$ 的限制，大概是平面内矩形加，每个询问相当于单点查询。对每个 $2^p$ 分别开一棵主席树，从而可以支持在线回答询问。同样由于区间无交，总复杂度也是 $O((n+q)\log n)$ 的。另外为了快速查询区间最高位，可能需要用 ST 表维护区间最大值，做到 $O(n\log n+q)$。
然后仔细看了一眼我代码，猛然发现理论复杂度瓶颈在查询单个值最高位的 $O(n\log V)$，抽象。使用 __builtin_clzll 做到 $O(1)$ 之后总时间复杂度为 $O((n+q)\log n)$。
原题
P12559。
09.29
单打 ACM 了说是，自己过了四个题。C 太唐了，G 我唐了，其他还行，发挥正常。
A 酒吧
题意
给出 $n$ 个位置，每个位置有值 $a_i$，现需选择一部分位置标记，之后每个位置两边最近的标记位置值均会贡献到总和一次，求最大总贡献。多组数据，$n\le 5\times 10^5,\sum n\le 3\times 10^6$。
题解
首先 $1$ 和 $m$ 必选，否则选上答案一定不降，之后发现答案是 $\sum_{i=1}^{k-1} (p_{i+1}-p_i)(a_{p_{i+1}}+a_{p_i})$。考虑寻找其意义，将 $(i,a_i)$ 标在坐标系上，发现该贡献即两点连线与 $x$ 轴围成直角梯形面积的两倍。因此要最大化所有梯形面积的和，显然选上凸包上所有点最优，维护出凸包后计算答案即可。时间复杂度 $O(n)$。
原题
QOJ5500。
E 数论方程
题意
给定 $n,p$，求一组满足 $1\le x\lt y\lt z\lt p$ 且 $(x+y+z)(x^n+y^n+z^n)(x^{2n}+y^{2n}+z^{2n})\equiv x^{3n}+y^{3n}+z^{3n} \pmod p$ 的整数 $(x,y,z)$。多组数据，$T\le 10^5,n\le 10^9,5\le p\le 10^9$ 且 $p$ 为质数。
题解
三个未知数却只有一个方程，只需要求出任意解即可。考虑只找出一个主元，将其表示出来再由此构造解。令 $x=at,y=bt,z=ct$，代入并化简可得 $t=\frac{a^{3n}+b^{3n}+c^{3n}}{(a+b+c)(a^n+b^n+c^n)(a^{2n}+b^{2n}+c^{2n})}$。
这时只需找到 $(a,b,c)$ 使得 $a,b,c$ 两两不相等，且分数中四项均非零即可。可以证明若在值域内随机选择 $a,b,c$，单个式子为零的概率不超过 $\frac 14$，于是随常数次就可以找到答案。时间复杂度 $O(T\log n)$，来自计算过程中的快速幂。
原题
ARC158D。
F 野蛮 5
题意
给出一个森林，两人轮流操作，每次删掉一条边或一个点及其邻边，无法操作者负，问先手是否必胜。$n\le 2\times 10^5$。
题解
手玩一下感觉很有性质，这里直接给出结论：当且仅当 $n,m$ 均为偶数时后手必胜。证明考虑终止状态显然满足条件，接下来证明其他情况均可一步操作到 $n,m$ 均为偶数，而这种情况无法在操作一次后保持。分讨：
- $n,m$ 均为奇数：删掉一个叶子节点，$n,m$ 均减小 $1$。
- $n$ 为奇数，$m$ 为偶数：删掉一个度数为偶数的点，$n$ 减小 $1$。由于度数总和为偶数，点数为奇数，这样的点一定存在。
- $n$ 为偶数，$m$ 为奇数：删掉一条边，$m$ 减小 $1$。
- $n,m$ 均为偶数：删点和删边后 $n,m$ 分别为奇数，无法保持。
因此，操作时若 $n,m$ 不均为偶数，不断将其变成均为偶数即可取胜，结论得证。只读入 $n,m$ 即可输出答案，时间复杂度 $O(1)$。
第一次见不用读完输入的题。话说 LCA 还有 SG 函数做法，是本质相同的，只是推导过程略有不同，此处略去。
原题
QOJ2323。
H 醉晓生成树
题意
有一个 $n$ 个点的完全无向图，每条边有 $p_0$ 的概率不存在，有 $p_i$ 的概率边权为 $i$。对所有 $t\in[n-1,k(n-1)]$，求图的最小生成树边权和为 $t$ 的概率。多组数据，$T\le 200,n\le 40,k\le 4$，且 $n\gt 20$ 的数据不超过 $2$ 组。
题解
考虑类似最小生成树的求解过程，按边权从小到大依次加边。暂且抛开计算边权和不谈，求 $f_{t,i}$ 表示 $i$ 个点被不超过 $t$ 的边连通的概率。考虑从节点 $1$ 开始，考虑连通块拓展的过程，初始为 $1$ 点由不超过 $t-1$ 的边形成的连通块，再通过 $t$ 边接上一些由不超过 $t$ 的边形成的连通块。
考虑再维护一个转移系数 $g_{i,j}$，表示目前 $i$ 个点的连通块新加入 $j$ 个点的概率。按点数从小到大考虑，考虑到大小 $s$ 先用 $g$ 中小于 $s$ 的部分求出 $f_{t,s}$，再用 $f_{t,s}$ 更新 $g$。这正确是因为初始连通块至少包含 $1$ 点，因此接上的总大小不超过 $s$。
$f$ 的转移显然为 $f_{t,s}=\sum_{i=1}^s f_{t-1,i}\times g_{i,s-i}\times {s-1\choose i-1}$，即枚举初始连通块大小为 $i$。$g$ 转移时需要所有新连通块间边权大于 $t$，新连通块与初始连通块间边权不小于 $t$，且存在至少一条 $t$。同时由于大小相同的连通块无法区分，加入 $k$ 个 $s$ 时还要额外除以 $k!$，防止算重。具体转移式此处略去，容易发现该 DP 的总复杂度为 $O(kn^3\log n)$，瓶颈在求 $g$ 时每个 $(i,j)$ 枚举所有 $(s,k)$，而 $(s,k)$ 的数量为调和级数的 $O(n\log n)$。
考虑将最小生成树的边权和考虑进来，比较暴力的方式是在 $f,g$ 中加维，加入 $S$ 表示总边权和，转移只需要在 $g$ 内加入新连通块时额外加 $t$ 即可，其余转移会加上一个背包状物，答案为 $f_{k,n}$。由于 $S$ 为 $O(nk)$ 级别，这样总复杂度要乘上 $n^2k^2$，为 $O(k^3n^5\log n)$，比较爆炸。
对于这种转移复杂度较高的背包，可以考虑使用插值优化。具体地，不再在状态中维护 $S$，转而直接维护一个多项式 $F(x)=\sum_{S=0}^{nk} p_S\cdot x^s$，其中 $p_S$ 表示边权和为 $S$ 的概率。然而直接用多项式乘法转移还是慢，即使上科技也得多带 log。由于多项式次数为 $O(nk)$，直接取 $x\in[0,nk]$ 分别代入求出最终 $F_{k,n}(x)$ 的值，这样转移时只有数字的转移，单轮复杂度仍为 $O(kn^3\log n)$。最后对 $F_{k,n}(x)$ 插值求出系数即为答案，这里复杂度为 $O(n^2k^2)$，于是总复杂度优化到了 $O(k^2n^4\log n)$，可以通过。
J 开拓
题意
交互。有一棵 $n$ 个点的树，每次可询问一个点集，得到其虚树叶子节点的编号和及其中之一的编号，还原整棵树。$n\le 1000$，询问次数不超过 $10^4$。
题解
$10^4$ 大概是 $O(n\log n)$ 级别，这启发我们使用二分状物。首先第一次询问整棵树 $S$，可得到 $u$ 节点为叶子，以及目前叶子节点编号和 $x$。将 $u$ 放入待连边集合 $T$ 并从 $S$ 中删除得到 $S'$，同时更新 $x$ 为 $x-u$。
之后查询 $S'$ 得到新的叶子节点编号和 $y$。若 $x\ne y$ 则说明删去 $u$ 后产生了新的叶子 $v=y-x$，这时可从 $T$ 中找到若干 $v$ 的儿子，方式是二分出最短前缀使得 $S'$ 加上这个前缀后 $v$ 不为叶子，这可以通过一次询问判断。不断寻找直到不存在 $v$ 的儿子即可。由于每个点只会从 $T$ 中被找出一次，总次数是 $O(n\log n)$ 的，可能会由于中止寻找的那轮二分带点常数，然而还是能过的。
10.02
时间分配有些问题，也不好说，反正由于水平等各种原因没时间做 T4 了。
T4 魔法相机
题意
给出若干个区间 $[l,r]$，可选若干非负整数点 $p$，要求任意两点之间距离不小于 $s$，求最多能覆盖的区间个数。$n\le 2\times 10^5,s,r_i\le 10^9$。
题解
考虑暴力 DP，设 $f_{x,i}$ 表示考虑了所有 $r\le x$ 的区间，此时最后一个点为 $i$ 最多能覆盖的区间个数。当从 $f_{x-1}$ 转移到 $f_x$ 时，有 $f_{x,x}=\max_{j=0}^{x-s}f_{x-1,j}$，之后枚举所有 $r=x$ 的区间，并对 $[l,x]$ 内的 $f_{x,i}$ 加一。
$n$ 次后缀容易使用线段树维护，然而前缀查最大值 $V$ 次太多了，无法接受。考虑寻找关键点，并只在这些点上转移。显然区间左端点 $l$ 均可能成为最值，然而这还不够，$l+m$ 处可能继承 $l$ 的信息，因此 $l+m$ 应该作为辅助点进行转移。然而辅助点也可能产生新的辅助点，数量还可能很多，还要优化。
考虑一个辅助点 $x$，若上个转移点为 $y$ 且 $f_x\le f_y$，则 $x$ 被 $y$ 支配，即之后 $f_y$ 一直不小于 $f_x$。证明考虑存在 $y\lt l\le x$ 的区间加时，$f_x$ 才可能变得比 $f_y$ 大，然而此时上个关键点变为 $l$，因此这种情况不存在。于是用堆维护所有转移点和区间，根据上述条件 $f_x\gt f_y$ 加入新点即可。
该做法正确性没有问题，然而关于时间复杂度，可以证明转移点的个数是 $O(n)$ 的，但我不太会证，感性理解是每 $O(1)$ 个点 $f$ 值就会增加，同时答案不超过 $n$。题解区有一些不太完整的证明，没看明白，不管了，总之用动态开点线段树可以做到 $O(n\log n)$。
原题
CF542B。
T5 小小的希望
题意
给定一棵树，父亲数组 $f$ 满足 $f_{i-1}\le f_i\lt i$，$q$ 次询问区间 $[l,r]$ 内 LCA 仍在区间内的点对点权乘积之和，即 $\sum_{x=l}^{r}\sum_{y=l}^r [l\le L(x,y)\le r] a_xa_y$，强制在线。$n,q\le 2.5\times 10^5$。
题解
由于 $f_i\lt i$，所以当 LCA 在区间内时，路径上的所有点均在区间内。因此区间内的点构成若干个连通块，每个连通块内两两选点均合法，贡献为 $(\sum a_i)^2$，所有连通块贡献和即为答案。另外还有 $f_{i-1}\le f_i$ 的限制，这说明树的节点编号形成 BFS 序。
考虑设 $t_i$ 表示 $i$ 点当前块的 LCA，$s_i$ 表示以 $i$ 为 LCA 的块 $a$ 的和。类似莫队移动端点，右端点改变时容易找到其对应 $t_i$ 并更新，复杂度 $O(1)$。然而左端点改变时需要合并新点的所有儿子，复杂度为 $O(d_i)$，其中 $d_i$ 为 $i$ 点度数。因此分块时除了要保证每块点数不超过 $B$，还需要保证 $\sum_{i=L+1}^r d_i\le B$。于是从后往前分块，每当某个限制爆掉就分成一个块。由于点数和 $\sum d$ 都是 $O(n)$ 的，总块数仍是 $O(\frac nB)$，可能要带上两倍常数。、
这时使用回滚莫队，每次先拓展右端点更新，再拓展左端点合并，实时维护当前 $\sum(\sum a_i)^2$ 即可。然而本题强制在线，考虑预处理全部 $O((\frac nB)^2)$ 对块间信息，每次取出信息再移动端点。需要知道的信息有右边块每个点的 $t_i$ 及 $s_{t_i}$，左边块每个点所有儿子的 $s_v$，共需要 $O(B)$ 的空间，可能有三四倍常数。取 $B=\sqrt n$ 可得理论最优时空复杂度 $O(n\sqrt n)$。然而空间常数过大炸掉了，卡不过去，于是开到 $B=1.55\sqrt n$ 后时空都极限过了，不管了。
10.03
T3 应该想到括号树的，最大败笔。然而这两场都没挂分，爽了。
T3 数括号
题意
有一个长为 $2n$ 的括号串 $s$，每次新增一条限制 $l,r$，表示最终括号序列中 $s_l,s_r$ 匹配，求每次增加限制后的合法括号序列数，保证有解。$n\le 5\times 10^5$。
题解
考虑所有匹配的括号对，若其内部无匹配括号，则内部一定是合法括号序列，用卡特兰数即可计算。之后可删掉这些位置，又会产生新的极小括号对。这样一直做下去就能求出答案。
考虑该过程实际上在干啥，发现将所有已知配对建成括号树，之后每个点内所有不在其子树内的位置形成一个合法括号序列，可以用卡特兰数直接计算。然而正着向括号数中加匹配比较困难，考虑用最终括号序列建树，之后倒着删树上的点，每次需要找到其当前父亲并修改其位置数。用树上并查集即可实现该操作，时间复杂度 $O(n\lpha(n))$。
T4 异或数组
题意
给定数组 $a$，保证 $0\le a_i\lt 2^m$。每次询问给出 $l,r$，求 $\max_{x=0}^{2^m-1}\min_{i=l}^r(x\oplus a_i)$。$n\le 10^5,q\le 5\times 10^5,m\le 50$。
题解
考虑单次询问怎么做，可以建出 Trie 树并在上面 DP，若当前点只有一个子树，则该位可为 $1$，再递归进该子树求解；否则该位必为 $0$，可选择一个子树作为后面位的贡献。实现上类似树形 DP，时间复杂度 $O(nmq)$。然而这告诉我们最终答案一定在 Trie 树上（虽然事实上所选的 $x$ 应该恰好是该节点的补集），启发我们改为对每个 $a_i$ 考虑。
具体地，对每个 $a_i$ 统计答案，则需关注 Trie 中其到根的路径上所有点，若没有兄弟节点则该位可产生贡献。于是找出 $l_{i,k},r_{i,k}$ 表示 $i$ 两边最近的 Trie 树上第 $k$ 位邻居，当且仅当 $L\le l_{i,k}\le i\le r_{i,k}\le R$ 时选择 $a_i$ 会产生 $2^k$ 贡献。注意到若 $i$ 不在区间内则贡献一定不优，于是与 $i$ 有关的限制可以删去，只剩 $L\le l_{i,k}\le r_{i,k}\le R$。
$l,r$ 各有 $m$ 个限制，两边共有 $O(m^2)$ 种可能的限制情况，也就是 $O(m^2)$ 个 2-Side 矩形 checkmax，单点查询。这可以使用扫描线维护前缀修改并单点查，用树状数组可以做到 $O(nm^2\log n+q\log n)$。然而发现前一项很大而后一项不大，使用 $O(1)$ 修改 $O(\sqrt n)$ 查询的分块可以平衡到 $O(nm^2+q\sqrt n)$，可以通过。
10.06
打得最好的一集。没挂而且暴力怎么过 $85$？反正 rk1，爽了。
T4 神谕
题意
给出一棵广义线段树，对其进行区间加操作，询问某个点目前的标记值。$n,q\le 2\times 10^5$。
题解
考虑用更简洁的方式刻画标记的加入和下传，关注 $l-1$ 和 $r+1$ 两条链，求出其 LCA，则 $l-1$ 到 LCA 路径上的点不在路径上的右儿子会被打标记，$r+1$ 同理。同时这些点到根的路径要下传标记，这可以找到两条链上有对应儿子的最深点，改为这两个点到根的路径清空标记，这会导致对其邻域打标记。
暂且放下实现不表，先分析一下标记下传的总次数。若 $u$ 点存在一个标记 $x$，则不管是直接加还是下传下来的，一定是某次在其兄弟子树内的操作导致的；同理若要下传 $u$ 点的标记，一定是某次在其子树内的操作导致的。因此下传的总标记数不超过 $2 \sum_{u}\min(s_{lc_u},s_{rc_u})$，其中 $s_u$ 表示 $u$ 子树内的操作次数。根据启发式合并的复杂度分析，这是 $O(q\log n)$ 级别的。
再来考虑实现，先对其树剖，再开两棵线段树分别维护链的左右儿子加。操作时直接在对应线段树上对某点到根的路径加，则符合儿子限制的点标记为 $w_{fa_u}-w_u$，这可以保证真正被打上标记的点在链外。
某个点到根的路径清空标记时，依次处理从根到该点的链。注意不能每次将标记下传给儿子，这会使复杂度退化到暴力，还比暴力多个 log。需要按带标记的点将链分成若干段，每段都对邻域加上比其深度小的标记和。所以线段树需要维护标记点位置，我的实现可能还需要维护前两个标记点，还要注意跨过轻边的处理。单次复杂度为 $O(\log n(\log n+c))$，其中 $c$ 为标记点个数。于是总复杂度为 $O(q\log ^2n)$，可以通过。细节一车，5k 代码写了一天。
10.09
最大败笔是会 T4 但 MLE 了，之后还是要注意时空限制，避免失误。
T3 日历
题意
有 $n$ 个 $m$ 位十进制数满足 $a_i=a_{i-1}+1\bmod 10^m$，存在若干已知位，构造一个合法的 $a_1$。$nm\le 10%^5$。
题解
注意到从后往前第 $i$ 位每 $10^{i-1}$ 行会加一，于是超过 $\log_{10}n$ 的位最多只会加一次。考虑对后 $5$ 位暴力枚举所有合法的 $a_1$，则这些位上每个限制形如 $a_1\bmod 10^j$ 在一个区间内，差分即可判断合法性。
枚举合法 $x$ 后可算出在第 $h$ 行向前进位。这时再枚举进位到第 $w$ 列，要求 $(h,w)$ 右上角全为 $9$，右下角全为 $0$，第 $w$ 列在 $h$ 上方为 $x$，下方为 $x+1\bmod 10$，且所有行的前 $(w-1)$ 列均相同。一个角全为某数可以用前缀和预处理，其余可预处理每列的限制情况。时间复杂度 $O(P+nm)$，其中 $P=10^5$。
T4 奶龙哞叫
原题：P11459，题解见【学习记录】凸优化。
注意这种分治结构不用 $O(n\log n)$ 的空间，可以每层只分配两个 vector，在 $u$ 点处分别将下层的空间分给两个儿子使用，合并到 $u$ 后就用不到了。由于第 $i$ 层单个节点所用空间为 $O(\frac n {2^{i-1}})$，总空间复杂度只有 $O(n)$，在本题中为 $O(nL)$。
10.11
整体还行，但 T3 犯唐写麻烦了，不然可能还能多冲点 T4 的。
T4 冒泡排序二合一
题意
给定排列 $a$，$q$ 次询问对 $[l,r]$ 区间进行 $k$ 轮冒泡排序后，$x$ 值的位置或 $a_x$ 的值。$n,q\le 6\times 10^5$。
题解
对于求 $x$ 值的位置，考虑转为两个 $01$ 序列，分别为 $b_i=[a_i\ge x]$ 和 $c_i=[a_i\gt x]$，对 $b,c$ 分别做 $k$ 轮冒泡排序后，两者不同的位置即最终 $x$ 的位置。此时若 $x$ 为 $b$ 中前 $k$ 个 $1$，则 $b$ 的第 $(k+1)$ 个 $1$ 不动，而 $c$ 的该位置作为第 $k$ 个 $1$ 移走了，于是有且仅有 $c$ 序列该位置前的 $0$ 最终在 $x$ 之前。
若 $x$ 不为 $b$ 中前 $k$ 个 $1$，则两序列该位置均不动，因此 $x$ 只会向左移动 $k$ 位。综上需要求区间内第 $k$ 个 $1$ 的位置，离线后按值从大到小扫描线，用树状数组维护 $01$ 序列并在上面二分即可，复杂度 $O((n+q)\log n)$。
对于求 $a_x$ 的值，显然若其在后 $k$ 个位置内，则一定是对应排名的数，即区间第 $r-k+1$ 大值。否则有 $x+k\le r$，考虑用 $[l,x]$ 的区间和减去 $[l,x-1]$ 的区间和。不难发现 $[l,x]$ 的区间和为 $[l,x+k]$ 区间内除前 $k$ 大外的和，证明可按 $[l,x+k]$ 区间第 $k$ 大转为 $01$ 序列，最终 $[l,x]$ 内一定没有 $1$，因此一定是所有 $0$ 的和。
实现上可以使用主席树查询区间第 $k$ 大以及对应的和，可以在线回答询问。时间复杂度也是 $O((n+q)\log n)$ 的。
10.13
T4 太难了，拼尽全力无法战胜多项式做法/ll。结果两个 Div 都没人过，确实太难了。前边打得还行，没有挂分。
T4 圆周距离问题
题意
$n$ 个点的环，相邻两点距离为 $1$。一种选点方式的代价定义为两两之间最短距离的最大值，求所有选 $k$ 个点的方式代价之和。$2\le k\le n\le 10^6$。
题解
枚举代价 $x$，设 $f_x$ 表示代价不低于 $x$ 的方案数，则答案为 $\sum_{x=1}^{\lfloor \frac n2\rfloor } f_x$，每种方案的贡献拆成了多段。然而这个难求，考虑求出 $g_x$ 表示代价不超过 $x$ 的方案数，则有 $f_x={n\choose k}-g_{x-1}$，于是求 $g$ 即可。
环上比较难考虑，需要断环为链。考虑任取一个被选点放在 $0$ 处，之后将环放到 $[0,n-1]$ 上，求此时合法方案数。这样求出方案数后放回环中有 $n$ 种位置，然而每种方案还会被 $k$ 个点各计算一次，于是最后还要乘上 $\frac nk$。
当计算距离不超过 $x$ 的答案时，显然只能在 $[1,x],[n-x,n-1]$ 内选点，且两部分内部不会非法，只需考虑两部分之间的限制。若选了 $p\in[n-x,n-1]$ 点，则 $[p+x+1-n,p-x-1]$ 内无法选点。注意到左端点 $x+(p+1-n)$ 一定在 $[1,x]$ 内，且长度均为 $d=n-2x-2$。于是将 $[n-x,n-1]$ 整体向后平移 $x+1$ 格到与 $[1,x]$ 重合，之后考虑长为 $x$ 的选择。
将移过来的点看成黑点，本来在 $[1,x]$ 内的点看成白点。现要从 $x$ 个点中选 $(k-1)$ 个并染成黑白两色，要求黑点之后 $d$ 个不能是白点。于是枚举黑色变为白色的次数 $i$，一定有 $id\le x$。在开头放一个白点，结尾放一个黑点，强制分成 $(2i+2)$ 段，于是分段方案可用隔板法计算为 $k\choose 2i+1$。之后先从 $x$ 个点中删掉 $id$ 个分隔符，从剩下的位置里选出 $k-1$ 个位置，再将分隔符插回分界位置即可，方案数 $x-id\choose k-1$。
于是有 $g_x=\sum_{i=0}^{\min(\lfloor \frac xd\rfloor,\lfloor \frac {k-1}2\rfloor)} {x-id\choose k-1}{k\choose 2i+1}$，预处理阶乘即可单次 $O(1)$ 计算，枚举量是调和级数的 $O(n\log n)$，可以通过。
原题
AGC068A。
10.16
T4 太难了，无法战胜，史哥太强了。整体还行，T5 看起来可补，之后有时间再说吧。
T4 放球程序
题意
有 $n$ 个球和 $n$ 个盒，编号均为 $1$ 到 $n$，初始可任意将球放到盒内。要求对 $i$ 从 $1$ 到 $n$ 依次操作，每次拿出 $i$ 盒内的球并任意排列成 $p_k$，之后同时将所有 $p_j$ 球放到 $p_{j+1\bmod k}$ 盒中。给出最终每个球所在盒的编号 $a_i$，判断是否可能出现该最终局面。多组数据，$\sum n\le 2.5\times 10^5$。
题解
发现顺序操作时自由度太高了，初值和过程中的排列顺序均难以确定，于是考虑倒着做，这样初始状态确定了。将状态用图表示，即球编号 $i$ 向所在盒编号 $a_i$ 连边，形成基环树森林。则对 $i$ 操作时所有指向 $i$ 的点均断开，再以任意顺序连成一个环；倒过来考虑时即找到一个环，将其断开并全部指向 $i$。
注意到上述两操作并不等价，原因是前者要求取所有指向 $i$ 的点，而后者没有限制这一点。仔细思考后发现只有两种情况合法，分别是 $i$ 点入度为 $0$ 或 $i$ 点在环上且入度为 $1$。前者可任意选环操作，后者必须选 $i$ 点所在的环，这对应操作前 $a_i=i$ 形成自环，会将其操作后环上前驱代表的球留在 $i$ 盒内。
于是出现了新的自由度：$i$ 点不在环上时可任意选环。猜想选 $i$ 所在连通块的环最优，手推发现选其他环时，除 $i$ 点外所有点的可操作性均不变；选所在连通块的环时，$i$ 点到环路径上入度只比限制多 $1$ 的点由不可操作变为可操作，其余点仍不变，于是这可能使局面变得更可操作，一定是最优的。
于是有了一个确定过程：从初始 $(i,a_i)$ 形成的图开始，倒序操作所有 $i$。每次先检查入度是否合法，不合法则无解；否则找到该连通块内的环，将其断开并全部指向 $i$，过程中修改入度。若能进行完 $n$ 次操作则有解。直接模拟该过程，暴力跳后继找环，复杂度可证明不超过 $O(n\sqrt n)$，事实上跑得特别快，证明如下（By Kevin090228）：
每次操作遍历操作点到环路径上和环上的所有点。由于路径上的点在操作后会变到环上，只分析每次操作环长 $L$ 的总和即可，即复杂度为 $O(\sum L)$。设局面 $S$ 的势能 $V(S)=\sum r_i^2$，即所有点入度的平方和。操作会使环上点的入度减 $1$，势能减小 $\sum_{t\in C} r_t^2-(r_t-1)^2=\sum_{t\in C} 2r_t-1$，由于全局入度和为 $n$，这是不超过 $2n$ 的；同时操作点 $x$ 入度增加环长 $L$，势能增加 $(r_x+L)^2-r_x^2=2Lr_x+L^2$，这是不低于 $L^2$ 的。
由于势能 $V(S)$ 上界为 $n^2$ 且 $n$ 次操作总减小量不超过 $2n^2$，总增加量一定不超过 $3n^2$。忽略 $2Lr_x$ 这一项，有 $\sum L^2\le 3n^2$，根据柯西不等式可得 $\sum L$ 至多是 $n\sqrt n$ 级别的，于是复杂度 $O(\sum L)$ 不超过 $O(n\sqrt n)$。
还有另一种做法，考虑进一步刻画合法局面，注意到操作点 $i$ 时要求 $i$ 没有环外入度，因此对于 $i$ 点不在环上的前子树 $u$，若其所有点编号均小于 $i$，则 $i$ 点操作前该子树不变，$i$ 点会由于 $(u,i)$ 存在而无法操作，必然无解。于是对于每个点 $i$，其每个子树 $u$ 最大值 $w_u$ 均需满足 $w_u\gt i$，才有可能有解，这是一个必要条件。
至于充分性，感性理解若满足条件，则每个子树内都有点操作过，从而 $(u,i)$ 这条边曾被纳入环中，不再构成限制，因此 $i$ 点此时可以操作，不太会严格证明。总之这个条件是充要的，据此可判断合法性，DFS 即可找出环并求出所有 $w_u$，时间复杂度 $O(n)$，然而没跑过上种做法。
原题
AGC068C。
10.18
T4 太难了，无法战胜。整体还行，T5 没看而且似乎比较思维，于是弃了。
T4 优美子数组
题意
定义数组 $b$ 划分的优美值为每段和的绝对值最小值。给定数组 $a$，要求支持单点修改，查询区间最大优美值。$n,q\le 10^6$。
题解
考虑优美值如何计算，分段方案的每一段均有正或负的权值，显然相邻段同号一定不优，可以将其合并，于是首先调整为正负交替。再注意到每相邻四段 $a,b,c,d$ 一定能将 $b,c$ 中绝对值较小的一个与两边合并，这也是不劣的。于是最终不超过三段。还能注意到此时若中间段绝对值不严格最大，则合成一整段更优。
综上，只能分一段（区间和），分两段（从前缀和最大最小值分开）或分三段且中间段绝对值严格最大。前两种均容易使用线段树维护，问题在于第三种的求解。考虑枚举分界线，钦定两个分界点在线两侧，则一定会选择从外侧起前 / 后缀和最值位置断开。
更具体地，对数组 $b_m$，其分三段正负正的最大优美值为 $\max_{i=0}^n(\min(p_i,s_{i+1}))$，其中 $p,s$ 分别表示前 / 后缀内前 / 后缀和的最大值，负正负同理。这显然能取到最优解，同时由于中间一段绝对值不最大时不优，这也不会比实际最优解大，于是这样求是对的。
根据定义，$p,s$ 分别不降和不增，于是最大值一定在两者图像交点处取到。具体地，若在序列上可对 $i$ 二分，找到第一个大小关系变化的位置。在线段树上可取出所有节点，先对这些位置二分出交点所在的段，再在线段树上进入该段二分，应该也能递归写，没试。总复杂度 $O(n+q\log n)$。
原题
P12554。
10.20
怎么四个全会，怎么挂了两个，被 corner case 爆了。离 AK 最近的一次，不过这也是为什么我们要认真处理细节，之后需要注意。
鲁ICP备2025150228号