本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-19 19:52:56
10.23
兵败如山倒。T3 Dijkstra 开成大根堆是什么玩意，T4 太难了不会，还挂了十分。还是要注意细节吧。
T3 暗符「Demarcation」（境界线）
题意
给出一个网格，给定起点和终点，每次移动会将当前位置标记为障碍，然后向某个方向走到障碍处停下，求走到终点的最少移动次数。$n,m\le 10^3$。
题解
考虑从起点开始走的情况，注意到通过来回走可以到达中间没有障碍的同行列点，代价从两边往中间递增，通过调整可证明以此为代价能取到最优解，且不会比答案小，直接 Dijkstra 可以做到 $\mathcal O(n^3\log n)$ 的复杂度，用 $n$ 个队列代替堆可以做到 $\mathcal O(n^3)$。事实上前者甚至都能过。
前缀和优化建图，注意到每个点向相邻所有点连 $2$，向一步能走到的点连 $1$ 即可表示整张图。Dijkstra 复杂度 $\mathcal O(n^2\log n)$，用 $3$ 个队列代替堆可以做到 $\mathcal O(n^2)$。
原题
AT_joisc2016_j。
T4 暗符「Dark Side of the Moon」（月的阴暗面）
题意
给定一个长宽均为 $120$ 的网格，每个格有向下或向右的方向，初始均向右，且 $(0,0)$ 位置有标记。每个时刻所有标记按照所在格的方向移动，并将原位置的方向变成另一种，之后在 $(0,0)$ 生成一个新标记。$q$ 次询问 $t$ 时刻变化之后 $(x,y)$ 上是否有标记。$q\le 10^4,x,y\le 120,t\le 10^{18}$。
题解
太难了，补完还是不知道为啥要这么做。整个变化非常抽象，难以对一个时刻的局面考虑，于是计算前 $t$ 个时刻经过 $(x,y)$ 的标记总数，差分一下就能得到 $t$ 时刻是否有标记。只有前 $(t-x-y+1)$ 个标记能到 $(x,y)$ 点， 设 $f_{i,j}$ 表示经过 $(i,j)$ 点的标记数，有 $f_{0,0}=t-x-y+1$。显然若 $(i,j)$ 被经过 $x$ 次，有 $\lfloor \frac x2\rfloor$ 个会向下走，其余向右走，容易递推出 $f_{x,y}$，时间复杂度 $\mathcal O(\sum xy)$。
太难了。
原题
CF1733E。
10.25
ICPC 赛制，三人三机打得还行，CSP 之后还得加练。
B. Beautiful Dangos
题意
给出一个三色序列，可以重排一个区间内的元素，要求最终序列相邻元素不同，求选择区间的最短长度，判无解。多组数据，$\sum n\le 2\times 10^6$。
题解
显然只有最大出现次数 $c$ 满足 $c\gt \lceil\frac n2\rceil$ 时会无解，初始合法也容易判断，先判掉。之后对于原序列所有相邻相等元素，操作区间至少要覆盖两个元素之一，于是找到最靠前和最靠后的这种相邻元素，取最靠前的后一个 $L$ 和最靠后的前一个 $R$，操作区间一定满足 $l\le L,r\ge R$。此处可能有 $L=R+1$，不过不要紧。
现在还需判断每个区间是否合法，对于某种颜色 $c$，设 $s_i$ 表示其在前缀中出现次数，则区间合法当且仅当 $s_r-s_{l-1}\le \lceil\frac{r-l+1-[a_{l-1}=c]-[a_{r+1}=c]}2\rceil$，移项并整理可得 $(r-[a_{r+1}=c]-2s_r)+(2s_{l-1}-l-[a_{l-1}=c])\ge -2$，设两个括号内分别为 $g_r,f_l$，合法条件就转化成了 $g_r+f_l\ge -2$，非常简洁啊！
之后对于最小操作区间 $[L,R]$，可以用这种方式判断三种颜色是否合法，可以发现最多只会有一种字符非法。对这种字符尝试将区间向两边扩展，可以发现 $f,g$ 分别单调，双指针即可求出最短的操作区间。至于构造方案，每次选当前剩余个数最大的即可，有多种最大的优先选 $a_{r+1}$ 就好了，复杂度 $\mathcal O(n)$。
K. Killing Bits
题意
给定两个从 $0$ 开始长为 $n$ 的排列 $a,b$，每次操作可以选择一个排列 $c$，更新 $a_i\leftarrow a_i & c_i$，这里是按位与运算。判断 $a$ 能否在任意次操作之后变成 $b$。多组数据，$\sum n\le 5\times 10^4$。
题解
首先若存在 $b_i$ 不是 $a_i$ 子集则一定无解，若 $a,b$ 相同则有解。对于其余情况，注意到只要存在 $c$ 满足所有 $b_i$ 均为 $c_i$ 子集则有解，否则无解。证明考虑只要存在这样的 $c$，就可以分别将 $b_i$ 换到对应位置上，此时另一边变成了 $b_i$ 的超集，合法性不变，一定存在解。于是这个条件是充分的，必要性不会证，不管了。
这时需要求是否存在合法的 $c$，此时相当于一个二分图完美匹配，左部点是 $n$ 种取值 $x$，右部点是 $n$ 个 $b_i$，$x,i$ 间连边当且仅当 $b_i$ 是 $x$ 的子集。考虑优化建网络流图，即建出中转点 $y$，对所有 $y$ 向每一位 $1$ 变为 $0$ 的子集连流量无穷的边，之后 $x,b_i$ 分别连向相等的 $y$ 即可。最后 Dinic 跑一下是否有完美匹配就行，复杂度能过。
10.27
整体还可以，严肃学习 T4 的 MEX 性质。T3 有更好写的做法，如果不写平衡树会有更长的时间做 T4。
T4 隋唐测试
题意
给出长为 $n$ 的序列 $a$，$q$ 次询问某个区间 $[L,R]$ 内长度不超过 $k$ 的子区间的最大 MEX。$n,q\le 10^6$。
题解
MEX 定义为未出现过的最小值，考虑将每个值贡献到所有区间上。将区间按照 $l,r$ 两维画到坐标系上，则每个 $x$ 未出现的极长区间 $[L,R]$ 会贡献到 $L\le l\le r\le R$ 这个矩形（三角形）内，相当于其内部每个点对 $x$ 取最小值。这样的极长区间共有 $\mathcal O(n)$ 个。
由于是取最小值，直接从小到大考虑每个 $x$，则会将 $(L,R)$ 右下角的所有没填过的点均填上 $x$。这个过程中填过的轮廓始终是一个左下到右上的折线，于是可以用 set 维护拐点快速处理。
另外，每个区域大概是一个倒过来的阶梯形，由于询问是一个贴着直线 $y=x$ 的梯形，只要该区域能贡献给某询问，则询问的梯形一定包含某个阶梯拐点。于是只用阶梯拐点 $(x,y,w)$ 计算即可，这个拐点数量也是 $\mathcal O(n)$ 级别的。
之后把询问的梯形拆成右上方的三角形和剩余的平行四边形，前者对应 $r-k+1\le x\le y\le r$；后者将平行四边形向下压，即以 $r-l$ 为纵坐标，可得 $y-x\lt k,l\le x\le r-k+1$。前者对 $r,y$ 扫描线后是后缀查询，可以树状数组；后者对 $y-x$ 扫描线后是区间查询，只能线段树。总时间复杂度 $\mathcal O((n+q)\log n)$。
10.29
最后一场了，出得有点烂，因为「斜二倍增」是树上算法的“新优选”！但是 T4 确实好题啊。
T3 树练习题
题意
给出 $n$ 个点，分别有点权 $a_i$。$q$ 次操作，每次随机出两个点 $u,v$，若不连通则加入边 $(u,v)$，连通则询问 $(u,v)$ 路径上点权的非空最大子段和。$n,m\le 3\times 10^6$。
题解
最大子段和是半群信息，也就是说题目要求支持动态加边的树上路径半群信息查询。考虑暴力做法，即每次取出对应路径暴力查询。此时需要维护每个点的深度和父亲节点，使用启发式合并更新即可。由于随机加边的期望树高为 $\mathcal O(\sqrt n)$，复杂度为 $\mathcal O(n\log n+q\sqrt n)$，能过不少。
考虑静态树上路径半群信息查询方式，树剖难以动态加点，考虑使用倍增。传统倍增每个点有 $\mathcal O(\log n)$ 的信息，套上启发式合并复杂度为 $\mathcal O(n\log ^2n+q\log n)$，空间也有 $\mathcal O(n\log n)$ 的复杂度，爆炸了。
于是使用斜二倍增，设 $w_i$ 表示 $i$ 向上跳 $F(d_i)$ 步的信息及其对应祖先。之后倍增求出 LCA，同时合并路径信息即可。这里 $F(x)$ 定义为后树上其管辖节点长度，可以倍增预处理。这样每个点只需要维护一个信息，时间复杂度降为 $\mathcal O((n+q)\log n)$，空间复杂度 $\mathcal O(n)$，可以通过。
原题
P14302。
T4 无尽旅途
题意
若 $T$ 时刻在 $u$ 点，则该时刻结束时会传送到 $c_{u,T\bmod d_u}$ 点。给定 $c$，$q$ 次询问从 $T$ 时刻在 $u$ 起经过 $x$ 个时刻后停在哪个点。$n,\sum d\le 10^5,q\le 5\times 10^4$。
题解
这种问题考虑倍增，设 $f_{i,j,k}$ 表示在 $i$ 点且 $T\bmod d_i=k$ 的状态下走 $2^j$ 步到达的点。然而这个状态是有问题的，一旦走到 $d_u\gt d_i$ 的 $u$ 点，$k$ 记录的时间信息就不够用了，需要知道时刻对 $d_u$ 取模的结果。于是 $j$ 这一维需要开到 $\max d$，只能做到 $\mathcal O(nd\log V)$ 的时空复杂度，无法接受。
但由于 $d$ 为 $2$ 的整数次幂，一共只有 $\mathcal O(\log d)$ 种取值，于是信息不够用的情况只会发生这么多次。考虑改 $f_{i,j,k}$ 为走过 $2^j$ 个 $d$ 与 $i$ 相同的点时最终到达的点。由于可能卡在 $d_u\gt d_i$ 的点 $u$ 上，同时记录 $g_{i,j,k}$ 表示此时走的步数，这些信息容易按 $d$ 从小到大的顺序预处理。
查询时同样从高位到低位跳，如果被卡了就重新从最高位开始。注意过程中若跳不到 $d$ 相同的下一个点，需要暴力向后跳一步。显然被卡和暴力向后跳的次数均不超过 $\mathcal O(\log d)$，总时间复杂度为 $\mathcal O(\sum d(\log d+\log V)+q\log d\log V)$，空间复杂度为 $\mathcal O(\sum d\log V)$。
原题
P10198。
11.06
CSP 之后第一场，感觉还行。T4 太难，胡出来一个比较假的做法，跟正解有点关系，但正解是人能想出来的吗？
T4 雪符「Diamond Blizzard」（钻石风暴）
题意
给出一个内向基环树，每个点有点权 $a_i$，每次更新将所有满足 $a_i\le a_{p_i}$ 的 $a_i$ 同时增加 $1$。$q$ 次询问 $d$ 次更新后 $a_g$ 的值。$n,q\le 2\times 10^5$。
题解
设 $f_{i,j}$ 表示 $a_i$ 在 $j$ 时刻的值，有 $f_{i,0}=a_i,f_{i,j}=f_{i,j-1}+[f_{i,j-1}\le f_{p_i,j-1}]$。考虑 $p_i=\min(i+1,n)$ 的特殊性质，显然 $f_{n,j}=a_n+j$。考虑从后往前推出所有的 $f_i$，首先 $f_{i,j}$ 关于 $j$ 的变化可以画到坐标系里，且只有 $0,1$ 两种斜率。
关注第一次满足 $f_{i,t}=f_{i+1,t}$ 的时刻 $t$，若 $a_i\le a_{i+1}$，则 $t$ 之前 $a_i$ 一直增加，否则 $a_i$ 一直不变。这部分斜率是相同的，可以区间覆盖实现。至于 $t$ 之后，有 $f_{i+1,j}\le f_{i,j}\le f_{i+1,j}+1$，具体取决于 $a_{i+1}$ 第 $j$ 次有没有增加，画到图像上大概会形成若干平行四边形。
之后思路不太像人。注意到 $t$ 之后部分的差分数组是位移得到的，具体来说是在 $i+1$ 的差分数组开头插入一个 $1$，之后整体向后平移一位，手摸一下可以发现该结论是对的。整体向后平移可能能用平衡树维护，但比较困难，没有尝试。
尝试避免向后平移。考虑将 $f_i$ 图像向左平移 $1$ 得到 $g_i$，注意到现在有 $g_{i,j}=f_{i+1,j}+1$ 了，可以区间加实现。然而前半部分维护的是斜率（即差分数组），好像还是很难做，考虑再将 $g_i$ 向下平移 $1$，于是有 $g_{i,j}=f_{i+1,j}$ 了，后半部分直接不用管了，赢。
然而细节仍然有一车，首要的就是给 $g$ 一个更好的定义。令 $i$ 的深度 $d_i=n-i$，我们令 $g_{i,j}=f_{i,j+d_i}-d_i$，这样就实现了 $i$ 图像相对于 $i+1$ 图像向左和向下分别平移了 $1$。同时由于用深度定义，这也可以拓展到树上。
当然这里需要维护 $g_{i}$ 的差分数组 $h_i$。重新画图讨论转移，发现此时 $g_i$ 图像的 $j$ 点向上走需要 $g_{i+1,j+1}$ 严格大于 $g_{i,j}$，这和题目条件 $f_{i,j-1}\le f_{p_i,j-1}$ 是一样的。手推讨论之后发现若 $a_i\le a_{i+1}$，则找到 $h_{i+1}$ 第 $(a_{i+1}-a_i)$ 个 $0$，此处之前全覆盖成 $1$，后面不变；否则 $a_i\gt a_{i+1}$，需要找到 $h_{i+1}$ 第 $(a_i-a_{i+1}-1)$ 个 $1$，前面全覆盖成 $0$，后面不变。这可以用线段树二分和区间覆盖实现，这样就完成了特殊性质的做法。
至于基环树，由于环上最小值一定会一直增大，可以从此处断环变成一棵树。树上的话每个点只会受到根链上的点影响，同样用线段树维护，出子树时撤销修改即可，时空复杂度都是 $\mathcal O((n+q)\log n)$。然后会发现空间爆了，我的做法是部分标记永久化，大概是在修改时正常下传标记，查询和二分时均不 pushdown，而是直接用函数传参记录根节点到当前点路径上第一个覆盖标记，这样撤销次数大大减小，可以通过。
当然好像有区间赋等差数列的做法，那就是直接维护 $g$ 数组了，应该差不多。
11.08
T3 爆了 lower_bound 返回值的语法错误，之后注意。T4 太神秘了，已严肃学习。
T4 学习
题意
给出一个森林，点有点权 $a_u$，边有边权 $b_u$。标记一个点需要花费 $a_u$ 的代价，若其父亲已被标记，也可以花费 $b_u$ 的代价。标记随时可清除，且不能同时存在超过 $k$ 个标记点。要求树上的 $m$ 个点均被标记过，求最小代价。多组数据，$T\le 30,m\le n\le 5000,k\le 5$。
弱化版：每个点只能被标记一次，$T\le 5,m\le n\le 10^5,k\le 10$。
题解
判掉 $k=1$，此时答案为 $\sum a$；将 $b_i$ 对 $a_i$ 取 $\min$，同时以 $0$ 为树根且不标记，避免讨论。考虑标记点形态，$k=2$ 时标记 $u$ 点后可向下拓展到子节点，但是需要清除 $u$ 点标记才能接着向下，最终能覆盖毛毛虫形状内的点。定义单点是 $1$ 合法的，对于 $i\gt 1$，定义 $u$ 子树 $i$ 合法当且仅当存在一个儿子 $i$ 合法， 且其他儿子均 $(i-1)$ 合法，这也能解释 $2$ 合法的形状。
于是对于弱化版，设 $f_{u,i}$ 表示 $u$ 子树内关键点均被标记过，且从 $u$ 开始的拓展过程 $i$ 合法的最小代价。状态不考虑 $u$ 点代价，因为其取值受父亲影响。另外令 $f_{u,0}$ 表示 $u$ 不选时的最小代价。转移为 $f_{u,1}=f_{u,0}=\sum\min(f_{v,k}+a_v,f_{v,0})$，对于 $i\gt 1$，有 $f_{u,i}=\min(f_{v,i}+b_v+\sum_{t\ne v}\min(f_{t,i-1}+b_t,f_{t,k}+a_t,f_{t,0}))$，只需先对第二个式子求和，再找最优差值更新即可。最后若 $u$ 必须被标记，将 $f_{u,0}$ 赋为正无穷，复杂度 $\mathcal O(nk)$。
对于原题，同一个点可被学习多次，即可以从 $u$ 拓展到 $v$，在 $v$ 拓展的过程中扔掉 $u$，之后需要标记 $v$ 或其他子节点时再把 $u$ 标记回来。据此设 $f_{u,i,j}$ 表示考虑 $u$ 子树，用到了至多 $i$ 的空间，过程中 $u$ 的子节点拓展需要 $u$ 点标记 $j$ 次的最小花费。与上面相同，状态不考虑 $u$ 点代价，这会在父亲节点上决策。
这个状态在定义什么？其包含子树内其他点的标记次数和方式，记录过程中的最大空间消耗和 $u$ 用于拓展的标记次数，以便向上转移。由于空间越大越可操作，$f_{u,i,j}$ 随 $i$ 增大单调不增。另外 $f_{u,i,0}$ 并非不标记 $u$，而是已经考虑的过程没有用 $u$ 拓展，还没有因此标记过 $u$。最终 $f_{u,i,0}$ 的值是无意义的，事实上代表的是 $i'\lt i$ 的 $f_{u,i',y}$，该状态也不能转移给父亲。至于真的不标记，再设 $g_u$ 表示 $u$ 不用于拓展时子树内最小代价，此时子树内其他拓展过程均可使用 $k$ 的空间，不用记录。
由于从某点开始同时向多个子树拓展不优，可以依次处理每个子树，这样可用空间更大。于是可依次将每个子树 $v$ 的信息拼到 $u$ 上。具体地，新拼上一个子树 $v$ 时，有以下几种转移（$t_v$ 表示 $v$ 是否需要标记；均有限制 $i\ge 2,j\ge 0,y\ge 1$）：
- $v$ 从 $u$ 拓展来，且拓展过程中一直保留 $u$，$v$ 标记 $y$ 次：$f_{u,i,j}+f_{v,i-1,y}+yb_v\rightarrow f'_{u,i,j}$。
- $v$ 从 $u$ 拓展来，且 $v$ 不用于向下拓展：$f_{u,i,j}+g_v+t_vb_v\rightarrow f'_{u,i,j}$。
- $v$ 部分从 $u$ 拓展来，过程中扔掉 $u$，$v$ 标记 $y$ 次，其中 $x$ 次从 $u$ 拓展：$f_{u,i,j}+f_{v,i,y}+xb_v+(y-x)a_v\rightarrow f'_{u,i,j+x}$，有限制 $0\le x\le y$。
- $v$ 不从 $u$ 拓展，标记 $y$ 次：$f_{u,i,j}+f_{v,k,y}+ya_v\rightarrow f'_{u,i,j}$；$v$ 不标记代价为 $g_v+t_va_v$，不如 2 优。
- $u$ 不向下拓展，$v$ 标记 $y$ 次：$g_u+f_{v,k,y}+ya_v\rightarrow g'_u$；$v$ 不标记：$g_u+g_v+t_va_v\rightarrow g'_u$。
最难理解的可能是转移 3，即 $v$ 用了全部的 $i$ 空间，此时每次从 $u$ 拓展都要重新标记 $u$。这里状态第三维记录的是用于拓展的标记次数，理解了这一转移大概就能理解状态设计的方式了。
至于初始值，开始的时候只有单点 $u$，所有值均为 $0$。$f_{u,1}$ 没有转移，注意到此时 $u$ 同样不能向下拓展，全部赋成 $g_u$ 即可。暴力实现的话，转移 2.4.5 的复杂度不超过 $\mathcal O(n^2k)$，可以接受；而转移 1 是 $\mathcal O(n^3k)$ 的，转移 3 不限制上下界是 $\mathcal O(n^4k)$ 的，均需优化。
对于转移 1，注意到是对所有 $y$ 取最小值，于是设 $h_{i}=\min(f_{v,i,y}+yb_v)$，转移就变成了 $f_{u,i,j}+h_{i-1}\rightarrow f'_{u,i,j}$。这样转移和 $h$ 的预处理都是 $\mathcal O(n^2k)$ 的了，可以接受。
对于转移 3，注意到下标变化只与 $x$ 有关，先用同样方法避免掉 $y$ 的枚举。具体地，对于确定的 $i,j,x$，会用 $y\ge x$ 的 $f_{v,i,y}+xb_v+(y-x)a_v$ 转移。将 $y$ 分离出来得到 $f_{v,i,y}+ya_v$，预处理其后缀最大值 $h_{i,y}$ 即可，复杂度同样是 $\mathcal O(n^2k)$ 的。之后转移为 $f_{u,i,j}+h_{i,y}+x(b_v-a_v)\rightarrow f'_{u,i,j+x}$。注意到 $j$ 一维显然不会超过子树大小，可以套用树形背包，复杂度就是 $\mathcal O(n^2k)$ 的了。
于是做到了 $\mathcal O(n^2k)$ 的时空复杂度， 单组数据就能过了。然而原题是 $30$ 组多测，根本不是人。不过还有常数优化！考虑一次 $i$ 合法的拓展，若新覆盖的点数少于 $i$，则其一定也是 $(i-1)$ 合法的，可以将其拼到某次 $i$ 合法的拓展上。因此一次 $i$ 合法的拓展至少新覆盖 $i$ 个点，于是 $f_{u,i,j}$ 的 $j$ 一维可限制 $j\le \lceil\frac {s_u} i\rceil$。加上这个常数大大减小，可以通过。
原题
P12777。
弱化版：P12734。
11.10
打得还行，T4 太鬼畜，随机扰动乱搞无法战胜。
T4 昡符「积木流彩」
题意
给定长 $n$ 宽 $m$ 的网格，保证 $n,m$ 均为奇数。局面定义为用 $1\times 2$ 的积木不重叠地铺成只剩一个空格，每次操作可选择当前空格相邻的一个积木，将其移动到该空格及原来某格内。给出初始局面和目标局面，构造操作序列实现两者间的转化。$n,m\le 2000$，要求操作序列长度不超过 $8\times 10^6$。
题解
将棋盘黑白染色，注意到空格始终在同种颜色的格子里，且每个积木均跨过两种颜色。考虑将局面建模成二分图匹配，黑白格分别对应左右部点，积木对应边。考虑初始和目标之间的关系，求出两个匹配的对称差，上面每个点度数不超过 $2$，只会形成环和链。又由于除空格外每个点度数恰为 $1$，所以只存在两图空格之间一条链，其余均为环。
再考虑操作在图上是什么，发现是从空格（失配点）起走一条非匹配边和一条匹配边，并将两者状态互换。于是先把上面所说的链走完，对称差中就只剩若干个环需要修改了。由于对称差中边的状态交错，环长也一定是偶数。
此时两个局面的空格位置相同，考虑在目标局面图上 DFS，遍历每个格子。一旦搜索到某个两局面中连边情况不同的格，说明该格在交错环上，此时立刻停止搜索并绕环走一圈，将该环转化到目标状态，同时空格也回到原点，再接着进行搜索。注意到整个图是一个连通块，DFS 会搜遍所有格，因此最终一定得到了目标状态。
至于操作次数，每次操作走两个点，每个点会搜到一次，搜完之后还有回溯，这部分不超过 $nm$ 次；清环操作经过每个点至多一次，这部分不超过 $\frac 12 nm$，总操作次数不超过 $\frac 32nm$，可以通过。
11.13
太困难了，T2 还不给大样例，暴力还挂了；T3 寒假做过同类题但还是没做出，大败而归了。
T2 毒瘤
题意
给定一个坐标系，初始有两个点一条边，所有边边权均为欧几里得距离。$q$ 次操作，修改加入一个新点 $c$，给出其坐标 $(x,y)$ 和两个点编号 $A,B$，保证 $A,B$ 间有边，之后加入 $A,c$ 和 $B,c$ 两条边；询问求两点间最短路。$q\le 10^5$。
题解
非常抽象地，考虑建一张新图，其中的点表示原图的边。加入一个点 $c$ 时，在新图中加入点 $(A,c),(B,c)$，并将这两个点向代表 $(A,B)$ 的点连边。显然每个点有唯一父亲，于是新图是一棵树。
考虑将原图中的路径长度表示到新树上，定义新树的一条路径权值为，找到新树路径的两个端点，对应回原图中的各两个点，记录两两之间的四条路径距离，前提是只经过该路径上对应边两端的点，且每条边至少经过一个点。
这样的话每次询问 $x,y$ 间最短路时，分别找出加入该点时对应的两条边，分别求四次树上路径信息，找到对应 $x,y$ 距离的值取 $\min$ 即为答案。有一些细节，若调到 LCA 之前的两个点与 LCA 在同一三角形内，需要特判直接走过去的情况。信息可以 $\min +$ 矩阵乘法维护，复杂度大常数 $\mathcal O(n\log n)$。
T3 异或
题意
给定序列 $a$，每次操作可以选择 $2\le i\le n$ 的 $i$，并修改 $a_i$ 为 $a_i\oplus a_{i-1}$。判断任意次操作后是否能使整个序列不降，若可以再求出单调不降序列数字种类数的最大值。多组数据，$T\le 30,n\le 10^4,a_i\lt 2^{30}$。
题解
手玩一下发现可对任意 $j\lt i$ 进行 $a_i\leftarrow a_i\oplus a_j$ 的操作，且不改变其他值。于是最终 $i$ 位置可以是 $a_i$ 异或上 $j\lt i$ 任意子集异或值。任意子集异或值可以用线性基维护，于是判定只需要贪心填最小数即可，每次求出 $U_{i-1}$ 内 $y\oplus a_i\ge f_{i-1}$ 的 $y\oplus a_i$ 作为 $f_i$，其中 $U_i$ 表示长为 $i$ 的前缀对应的线性基，可以做到 $\mathcal O(n\log V+\log ^2V)$，后者是线性基标准化的复杂度。
至于求最大值，考虑暴力 DP，设 $f_{i,j}$ 表示前 $i$ 个数内有 $(j+1)$ 种值时 $i$ 位置的最小值，用线性基支持同样操作即可转移，复杂度 $\mathcal O(n^2\log V+\log^2V)$。
注意到前缀线性基只有 $\log V$ 种，考虑对相同线性基整体转移。具体地，若 $i\in[l,r]$ 内的 $U_i$ 全相同，则在 $l$ 处暴力转移，这样的位置有 $\log V$ 个，复杂度 $\mathcal O(n\log^2V)$。对于 $[l+1,r]$ 内的转移，由于 $a_i$ 无法加入线性基，这部分的最终值均为 $U_l$ 中的任意值。
设 $d=r-l$，需进行相同的 $d$ 次转移，此时每次取相同数或线性基中后继最优。具体地，令 $f'{j}$ 表示目前 $(j+1)$ 种数的最小值在 $U_l$ 中的排名，$g'_j$ 表示转移 $d$ 次后最小值在 $U_l$ 中的排名，有 $g'_j=\min{j-d\le t\le j} f'_t-t+j$，用单调队列维护 $f'_t-t$ 即可快速转移。$f',g'$ 与值的转化需要在标准化线性基中查询排名和第 $k$ 小，总复杂度 $\mathcal O(n\log ^2V)$。
T4 符板
题意
给定 $n\times m$ 的字符矩形，有两个字符相同，方向不同的 $1\times l,l\times 1$ 矩形，需要在字符匹配的前提下密铺整个矩形，求合法矩形对应的 $l$ 集合。$n,m\le 1000$。
题解
注意到对于单个 $l$，合法字符串一定是第一列或第一行的前 $l$ 个字符，只需要考虑如何判断合法。对某个位置考虑，猜测若能横着填就横着填是对的。原因是若 $(i,j)$ 处能横着填，若这 $l$ 个位置均竖着填则模板串全同，否则若 $t$ 个位置竖着填，$(i+t,j)$ 开始横着填，则模板串前 $t$ 个字符相同且 $t$ 是其周期，模板串也一定全同。而模板串全同的情况只能覆盖全同的矩形，容易特判。
于是可以从左上到右下依次进行覆盖，若某个位置未覆盖则从此处开始分别向右、向下判断长为 $L$ 的串是否未被覆盖且合法，均不合法就寄了，否则能横着合法就横填，否则竖填。注意到字符矩形全同的情况也能判出来，不用特判。此时以 $\mathcal O(l)$ 的复杂度覆盖 $l$ 个点，所以单轮判断是 $\mathcal O(nm)$ 的。又由于只有 $n$ 或 $m$ 的因数可能合法，直接枚举就是小常数 $\mathcal O((d(n)+d(m))nm)$ 的，可以通过。
11.17
T2T3 是啥阴间，太困难。T4 倒是会但没调完，不管了。
T3 路标
题意
给定 $n$ 个长为 $m$ 的序列 $d_{i,j}$，表示 $\lfloor y_j-x_i \rfloor=d_{i,j}$，要求对于任意 $i,j$ 均有 $x_i\lt y_j$。求最多能选出多少行使得存在 $x,y$ 序列满足所有条件，保证答案不低于 $\frac n5$。$n\le 1000,m\le 200$。
题解
由于对答案大小有保证，可以随机某一行 $u$ 并钦定其必选，再尽量多选其他的。合法条件可转化为对于任意 $i,j$ 均存在 $e_{i,j}\in[0,1)$ 满足 $d_{i,j}=y_j-x_i-e_{i,j}$。然而最好让限制中不带 $x,y$，这样比较好处理。于是令 $a_{i,j}=d_{i,j}-d_{u,j}=x_u-x_i+e_{u,j}-e_{i,j}$，再令 $p_i$ 表示 $a_{i,j}$ 的最小值位置，有 $b_{i,j}=a_{i,j}-a_{i,p_i}=e_{u,j}-e_{i,j}-e_{u,p_i}+e_{i,p_i}\ge 0$。
由于 $d,a,b$ 均为整数且 $e\in[0,1)$，$b$ 数组只有 $0,1$ 两种取值。移项可得 $e_{i,j}=e_{u,j}-e_{u,p_i}+e_{i,p_i}-b_{i,j}$。于是需要存在 $e_{u,p_i}\in[0,1)$ 使得上式全在 $[0,1)$ 内，这要求 $e_{u,j}-b_{i,j}$ 的极差小于 $1$。又根据 $b_{i,j}$ 只有 $0,1$ 两种取值，这相当于要求所有 $b_{i,j}$ 为 $0$ 的 $e_{u,j}$ 小于 $b_{i,j}$ 为 $1$ 的 $e_{u,j}$。于是令 $S_i$ 为第 $i$ 行为 $1$ 的列号，要求选出最多的 $S$ 使得两两之间存在包含关系。
于是按 $1$ 的个数排序后 DP，单轮复杂度 $\mathcal O(\frac{n^2m}w)$，还要乘上随机次数的常数，这里取 $25$ 就过了。
原题
P14055。
11.20
打得还行，手感火热！但是 T4 把没判特殊性质的暴力交上去了，之后要注意。
T3 幻幽「Jack the Ludo Bile」（迷幻的杰克）
题意
$n$ 条射线绕中心形成一个环，有 $m$ 条连接相邻两射线的线段，两端点到中心距离相等。初始选择某射线向外走，遇到线段时强制走到另一端。可以任意加入满足同样限制的线段，对每个 $i$ 求初始在 $i$ 射线上走，最终走到 $s$ 射线无穷远处需要加入的最少线段数。$n\le 2\times 10^5,m\le 5\times 10^5$。
题解
由于是强制走过线段，若按到中心的距离从大到小考虑，则每条线段相当于交换相邻两条射线的终点编号，要求即最终 $i$ 射线终点为 $s$。考虑按该顺序 DP，设 $f_{i,j}$ 表示考虑了前 $i$ 条给定线段，当前 $j$ 射线终点为 $s$ 的最小加入数，有初始值 $f_{0,i}=\min(\left|s-i\right|,n-\left|s-i\right|)$。
至于转移，先交换 $f_{i-1,t_{i}},f_{i-1,t_{i}\bmod n+1}$。之后还要考虑线段的加入，有 $f'{i,j}=\min f{i-1,k}+\min(\left|j-k\right|,n-\left|j-k\right|)$。由于只有两个位置变化，只需要尝试用较小值向外更新，并尝试更新较大值，可以做到单次 $\mathcal O(n)$，总复杂度 $\mathcal O(nm)$，答案即 $f_{m,i}$。
观察这个 DP 的形式，注意到差分数组只有 $-1,0,1$，否则一定可以更新，于是考虑维护差分数组 $g_i=f_{i}-f_{(i+n-2)\bmod n+1}$。设 $x=t_i,y=t_i\bmod n+1$，$g_y=0$ 时交换没有影响，以下以 $g_y=1$ 为例，$g_y=-1$ 是类似的。
首先考虑 $x$ 位置的变化，$f_x$ 先由于交换增加 $1$。此时若 $g_x=1$，则 $f_x$ 还会被上个位置拉回来，于是 $g_x$ 仍为 $1$，$g_y$ 变成 $0$；否则就拉不回来了，$g_x$ 增加 $1$，$g_y$ 变成 $-1$。至于 $y$ 减小对其他位置的影响，显然无法更新前面元素，画图可得从 $y$ 向后找到首个非 $1$ 位置 $z$，此前的 $f$ 值均会减一，在 $g$ 上的影响即 $g_z$ 增加 $1$。
这需要查询 $y$ 后面首个非 $1$ 位置，在 $g_y=-1$ 时是前面首个非 $-1$ 位置，用 set 分别维护两种下标，单点改的时候也修改 set 即可。另外若只考虑给定操作会将 $s$ 交换到 $t$，则一定有 $f_{m,t}=0$，从该位置按 $g$ 数组推出 $f$ 即为答案，复杂度 $\mathcal O(m\log n)$。
原题
P9447。
T4 幻象「Luna Clock」（月神之钟）
题意
给出数组 $a$，可任意次操作交换 $a_i,a_{a_i}$，求能得到的本质不同序列个数。$n\le 10^6,1\le a_i\le n$。
题解
直接上图，肯定是个基环树森林，每次操作相当于选择 $i$，然后 $i$ 直接指向 $a_{a_i}$ 并将 $a_i$ 连成自环。考虑把整个过程看成对边打标记，操作 $i$ 时要求 $a_i$ 非自环，此时标记 $(i,a_i)$ 这条边，之后实际的 $a_i$ 变为一直跳后继直到跳过一条非标记边到达的点。
可以发现每种对边标记的方式几乎能与序列一一对应，先抛开这个几乎不谈，主要限制是每个点的入边只能选一条，于是大概是 $\prod (r_i+1)$。然而问题出在环上，上述过程是无法标记环上所有边的，同时每种只有一条未标记边的方案对应的序列相同。
于是考虑直接在环上所有边均被标记的情况下统计这种方案，并减去只有一条未标记边的方案数，即 $\prod(r_i+1)-\sum r_i$。后面一项是枚举环上每条边作为未匹配边，钦定其余边均选在环上，该边不选在环上的方案数。不在环上的点另外乘上 $\prod(r_i+1)$，得到一个连通块的方案数。将每个连通块的方案数乘起来即为答案，复杂度 $\mathcal O(n)$。
原题
CF1863G。
11.22
还行，T3 或许应该做出来？之后这种和固定还是要考虑根号种不同值啊。
T3 再见了，所有的字符串
题意
给定一棵树，点有点权。$q$ 次询问给出序列 $b$，定义某个点的价值为根到其路径上的点权序列中，与 $b$ 序列完全相同的不重叠子串最大个数，求所有点的价值最大值。$n,q,a_i,\sum m\le 10^5$。
题解
先考虑链上单次询问，此时可 KMP 或哈希找到询问串的所有出现位置，之后需要满足相邻两个距离不小于 $m$，求最多能选多少。显然可以从左往右贪心，即先选最靠左的，之后依次选不低于上一个加 $m$ 的最小值。这个放到树上可以同样贪心，把方向改成从根到底即可。
于是对于 $m$ 均相同的情况，可以进行 DFS，维护当前点到根路径序列的哈希值，以及当前每种串的答案，出子树时撤销修改。由于每个点向上的字符串唯一，一共只有 $\mathcal O(n)$ 个串，用哈希表以这些串的哈希值为下标存储答案，单轮复杂度是 $\mathcal O(n)$ 的。
对于原问题，由于 $\sum m\le P=10^5$，询问串长种类数不超过 $\mathcal O(\sqrt P)$，于是直接跑这么多遍就是对的，复杂度 $\mathcal O(n\sqrt P)$，带哈希表常数，卡卡就过了。
原题
P11471。
T4 再见了，所有的增量挑战
题意
序列 $a$ 初始全 $0$，每次操作可将某个前缀或后缀加 $1$，代价为长度，求使 $a_i\ge b_i$ 的最小代价。$n\le 10^6,a_i\le 10^9$。
题解
由于总代价与数组元素和相等，直接求和尽可能小的 $a$ 即可，现要判断 $a$ 数组是否能被前后缀加操作构造出来。考虑将 $a$ 数组变成全部相同，且使相同的值尽可能大，$a$ 数组合法当且仅当该值非负。于是对于所有 $a_i\gt a_{i+1}$ 的位置，必须进行 $i$ 前缀操作 $a_i-a_{i+1}$ 次，后缀同理，进行完这些操作后序列非负则合法。
事实上，前后缀中进行完一种操作后，序列最小值在某一端且不再改变，于是只考虑一个过程即可。对于前缀，共进行了 $\sum \max(0,a_i-a_{i+1})$ 次操作，需要开头非负。不妨加入 $a_0=P\gt a_i$，于是限制变为 $\sum_{i=1}^n\max (0,a_i-a_{i-1})\le P$。注意到对每个两侧均高于本身的极长连续段，将其整体增高 $1$ 会使得式子左边增加 $1$，用单调栈求出所有的连续段后贪心选择即可，复杂度 $\mathcal O(n)$。
11.24
在家乱打的，怎么一堆原。T4 感觉牛的。
T4 【列阵】打卡
题意
给定一张无向连通图。到达某点需要有至少 $a_i$ 的钱，之后可以花费 $b_i$，求在每个点各花费至少一次的最少初始钱数。$n,m\le 10^5$。
题解
注意到一定会在最后一次经过某点时花费，否则调整到最后一次一定不劣。之后考虑倒着做，这样只能走已经花费过的点，且进入某点至少需要 $c_i=\max(0,a_i-b_i)$ 的金钱。
考虑维护目前能到的点集 $S$，初始只包含起点（即原问题的终点），同时维护当前值 $x$ 和答案 $r$。每次从 $S$ 中取出 $c$ 最小的点 $u$，若 $x<c$ 则补到 $c$，$r$ 也要增加相同值。之后 $x$ 加上 $b_u$，并将 $u$ 从 $S$ 中删去，将 $u$ 未加入过 $S$ 的所有邻点加入 $S$。答案为所有 $r$ 的最小值加上 $\sum b$，枚举起点后可用堆维护，复杂度 $\mathcal O(n(m+n\log n))$。
注意到该过程与最小生成树很像，是按 $c$ 从小到大拓展的。于是按 $c$ 值建出 Kruskal 重构树，这样该过程可以变成从叶子跳到根。又注意到跳的过程中对于点 $u$，需要额外加的值 $x$ 需满足 $s_u+x\ge w_{fa_u}$，于是 $x\ge \max(w_{fa_u}-s_u)$，DFS 过程中记录根到当前节点的 $\max$ 值，对叶子节点的答案取 $\min$ 再加上 $\sum b$ 即可，复杂度 $\mathcal O(n+m\log m)$。
鲁ICP备2025150228号