3.17

[ARC193D] Magnets

感觉很菜，比 C 菜多了。打的时候胡出来了，但是摆烂不想写。

一些简单的观察是一次操作是把一个段长度减 $2$，或者是两个相邻的段长度都 $-1$。还有一种是最左侧或者最右侧的段 $-1$，但是这种操作一定只会做一次。暴力枚举是否做左右减一的操作一共跑 $4$ 次贪心即可求出是否合法。

对于操作数，首先把区间缩成和 $b$ 的长度一样。然后除去开头结尾的操作，操作过程中中点是固定的，最后再调一下位置即可。

CF2077F AND x OR

变态。

考虑怎么判定合法。首先全相等合法，否则一定会操作一次。操作一次就能得到一个必要条件：$\exists i,j,d_i\subseteq d_j$。然后这个条件也是充分的，可以最后构造证明。

然后求出小于等于 $i$ 的最大值和次大值 $f_i,g_i$，然后做一个高维前缀和之后统计答案即可。

CF2077G RGB Walking

这太难了。

设三种边权和分别为 $f_1,f_2,f_3$，考虑求出三种颜色的所有边权分别的 $\gcd$，设为 $a,b,c$。则如果一条路径经过了所有点，则可以任意 $f_1+2a,f_2+2b,f_3+2c$。

所以首先找一棵树，遍历一遍，这样每个边都经过了 $0$ 次或者 $2$ 次，因此此时 $f_1\bmod{2a},f_2\bmod{2b},f_3\bmod{2c}$ 都是 $0$。

而从 $1$ 走到终点之后，$f_1\bmod{2a}$ 要么是 $0$ 要么是 $a$，$f_2,f_3$ 同理，一共 $8$ 种状态，所以可以求出来是否合法。

Strong Connectivity Strikes Back

首先考虑 DAG，重边可以删到只剩一条，然后剩下的一条边能删当且仅当把他删了之后他的起点还能达到终点。

对于一个 SCC 内部，一条边删掉之后如果 SCC 不会变，那这个边一定不能删。

3.19

CF2066E Tropical Season

好像不大难。

单组判定：从小到大排序，维护一个当前干净的水量 $s$。如果 $>s$ 的桶只剩不多于一个那就直接合法了。否则找到 $>s$ 的，相邻两个 $i,i+1$ 的最小差 $d$，若 $d\leq s$，则可以 $s=a_{i+1}$。然后不断进行 $s=query(1,s)$，query 返回值域在 $[1,s]$ 中的所有数的和。

拿值域线段树维护所有数，容易发现操作次数是 $\mathcal O(\log V)$ 级别的。所以复杂度是两个 $\log$。可以值域倍增分块做到单 $\log$。

CF1712F Triameter

先两边 dfs 求出 $f_i$ 表示到 $i$ 最近的叶子的距离。然后假设 $f=i$ 的集合是 $S_i$，那 $S_i$ 和 $S_j$ 之间的贡献就是 $\displaystyle \min(i+j+x,\max_{l\in S_i,r\in S_j}\text{dis}(l,r))$。

所以考虑维护当前答案 $ans$，枚举 $i$，不断尝试让 $ans$ 增大 $1$。对于 dis，可以求出点集内直径和点集后缀的直径，这样就可以用 $\mathcal O(1)$ 求了。需要一个 $\mathcal O(1)$ LCA。

CF1637H Minimize Inversions Number

非常困难。

首先对于 $k=1$，只需要找到单次贡献最大的。设 $d_i$ 表示只操作 $i$ 能让逆序对减少多少，显然 $d_i=\sum_{j<i}[a_j>a_i]-[a_j<a_i]$。这个可以简单求出来。

然后对于多组，如果选了一些 $d$，实际的意义是把选出来的子序列倒序过来拼在了最前面。所以假设选择的下标是 $p_1,p_2\dots p_k$，实际上逆序对数应该额外减去 $\sum_{i>j}[a_{p_i}<a_{p_j}]-[a_{p_i}>a_{p_j}]=\binom k 2-2\times \text{inv}(p)$。

然后核心结论是如果选择了 $i$，一定不存在 $j>i$ 且 $a_j<a_i$ 且没有选择 $j$。证明就是狂暴分类讨论。

调整法，找到 $j-i$ 最小的 $(i,j)$。尝试不选择 $i$ 并选择 $j$，对于每个 $k$，检查 $(i,k)$ 和 $(j,k)$ 的变化。

对于 $k<i$ 并且选了，$(i,k)$ 和 $(j,k)$ 相对顺序都没变，所以变化量是 $0$。

对于 $k<i$ 并且没选，$a_j<a_k<a_i$ 时，变化量是 $-2$，否则变化量是 $0$。

对于 $k>i$ 并且选了，$a_j<a_k<a_i$ 时，变化量是 $-2$，否则变化量是 $0$。

对于 $k>i$ 并且没选，$(i,k)$ 和 $(j,k)$ 相对顺序都没变，变化量是 $0$。

对于 $i<k<j$ 并且选了，一定有 $a_k<a_j$（否则 $(i,j)$ 不是最近的），变化量是 $-1$。

对于 $i<k<j$ 并且没选，一定有 $a_k>a_i$（否则 $(i,j)$ 不是最近的），变化量是 $-1$。

所以，其他所有数和 $i$ 或者是 $j$ 的逆序对数和的变化量非正。再加上 $(i,j)$ 本身的 $-1$，一定会更优。这样调整步数也一定有限。得证。

所以答案中的 $\text{inv}(p)$ 可以变为 $\sum_{i}\sum_{j>p_i}[a_{p_i}>a_j]$。是一个只和 $p_i$ 有关的值，所以算进 $f$ 里面就行了。只需要树状数组，复杂度 $\mathcal O(n\log n)$。

CF2068I Pinball

挺牛的。

考虑把图划分为若干个环，然后环之间连边权为 $1$ 的边跑最短路就是对的。阿巴阿巴。

CF2062G Permutation Factory

下标和 $p$ 之差取 $\min$ 可以看成任选一种移动方式来移动平面上的点。感性理解一下，可以看成花费 $k$ 的代价，移动一共 $2k$ 的距离。

CF1630F Making It Bipartite

容易发现合法的充要条件是不存在一个点同时存在因数和倍数。必要性显然，若 $x\vert y,y\vert z$ 则 $x\vert z$，这样就形成了一个三元环。充分性的话考虑如果每个点要么只有因数，要么只有倍数，那一个环上，一定是这两种点交错的，所以一定不存在奇环。

然后考虑拆点，一个点拆成倍数点和因数点，分别设为 $x_0,x_1$，表示一个点只能作为别人的倍数，或者只能作为别人的因数。然后如果 $x\vert y$，两者的合法存在方式是，$(x_0),(x_1),(y_0),(y_1),(x_0,y_1)$。

所以这样就是，$x_0$ 连边 $x_1$，$x_0$ 连边 $y_0$，$x_1$ 连边 $y_0,y_1$，求出这个图的最大独立集即为答案。

但是很遗憾，上面这个图并不是二分图，最大独立集不可求。考虑如果存在一个定向，把图定成一个偏序图（即若存在边 $x\rightarrow y,y\rightarrow z$，则存在边 $x\rightarrow z$），这个图的最长反链也就是最大独立集。可以定向为：对于每个 $x$ 连 $x_1\rightarrow x_0$ 以及对于每个 $x\vert y$ 连 $x_0\rightarrow y_0,x_1\rightarrow y_1,x_1\rightarrow y_0$。这个图的最长反链即为答案，dilworth 定理得最长反链即为最小链覆盖，dinic 跑最小链覆盖即可。

CF1693F I Might Be Wrong

I Must Be Wrong.

猜测不到只会操作 $c_0=c_1$ 的区间。不会证明：对于一次操作，假设操作区间中 $0$ 的个数大于 $1$ 的个数（否则可以 rev 再 flip，等价）。

画出折线图，$0$ 就是向右上走，$1$ 就是向右下走。如果第一个字符是 $0$ 那显然可以不操作他来减少代价，所以不断找到第一个 $1$ 的位置 $p$，找到他后面最后一个和他齐平的位置，操作这段区间。如果找不到，则一定有 $p>c_0-c_1$，此时可以加入 $p-(c_0-c_1)$ 个前缀，一次操作到最后就行了。不断重复这段过程，显然 $p$ 每次会增加至少 $1$，所以不劣。

这样按照上面的这个对整个序列贪心即可。

CF1684G Euclid Guess

首先如果 $3a_i\leq m$，可以直接构造一个 $(2a_i,3a_i)$ 的数对。

否则考虑构造一个 $(x+a_i,x)$，考虑其变化：$(x+a_i,x)\rightarrow (x,a_i)\rightarrow (a_i,x\bmod a_i)\dots$

看不出来什么？考虑再展开一步。令 $x\bmod a_i=y$。则可以构造 $x=y+a_i$，数对即为 $(y+2a_i,y+a_i)\rightarrow (y+a_i,a_i)\rightarrow(a_i,y)\dots$ 注意到可以令 $y$ 为 $a_i$ 的一个因数，这样只会加入 $a_i$ 和 $y$。而 $2a_i+y\leq m$，有 $y\leq \frac{1 }{3}m$。所以这构成了一个二分图，求出匹配即可。

3.24

[ARC195E] Random Tree Distance

流汗了，咋做过类似的还不会。

设 $f_u$ 为 $u$ 的期望深度，这个可以线性求。对于 $E(f_{\text{lca}(u,>u)})$，把 $u$ 和 $v$ 不断把深的那个向上跳。考虑 $v$ 第一次跳到 $\leq u$ 的位置，这个可以看成在 $[1,u]$ 里均匀随机。所以 $E(f_{\text{lca}(u,>u)})$ 和 $v$ 无关。

所以设 $g_u$ 表示 $E(f_{\text{lca}(u,>u)})$，有 $g_u=\frac 1 u(f_u+\sum_{i<u}g_i)$。

CF2089D Conditional Operators

jiangly 说这种题要打表。

令 $n$ 为序列长度。首先判掉 $n=3$，然后对于 $n\geq 5$，有解的充要条件是，$a_n=1$ 或者存在 $i<j,a_i=a_j=1$ 满足 $i$ 是奇数，$j$ 是偶数。对于 $n=5$ 可以验证出上述结论是对的。对于 $n>5$，考虑归纳构造。

对序列最后三个字符分类讨论。发现 $001,011,110,111$ 都满足把这三个合并之后是 $1$，那就可以直接合并。$000$ 和 $100$，这两个 $a_n\not=1$，所以前面一定存在上述满足条件的 $i,j$，容易发现直接合并也不会影响这个 $i,j$。所以除了 $010$ 和 $101$，其余六种情况都可以把最后三个直接合并。

对于 $010$，他的这个 $1$ 在偶数位置上，不能简单的抹去，因为他可能是合法的唯一的一个 $j$。所以加入倒数第四个字符。如果是 $0010$，可以操作 $(001)0$，这样这个 $1$ 仍然在。如果是 $1010$，可以操作 $1(010)$，这样也能满足还有一个偶数位置的 $1$。

对于 $101$，可以直接操作 $(*10)1$，这样最后一个位置仍然是 $1$。

归纳到 $n=5$ 的时候按照谁先合并分三种情况搜一下就行了。

CF2089E Black Cat Collapse

感觉 $n\in[60,80]$ 的题从来没想出来过。

先考虑倒着做，枚举 $i$ 表示序列长度。然后就有限制是编号为 $j$ 的只能在第 $\max(1,i-(n-j))$ 次及其之后选。然后限制最紧的那些点，就是选取的点的编号前缀最大值。那基于这个 DP，设 $f_{j,x,d}$ 表示当前选了 $j$ 个点，当前前缀最大值是 $x$，当前有 $d$ 个点确定了他要放在后面但是还没有放的方案数。$d$ 这一维是因为，从 $i$ 转移到 $j$ 的时候，需要钦定 $(i,j)$ 之间的点是否在以后加入。预处理 $trans_{x,y,k}$ 表示从 $x$ 转移到 $y$，$x,y$ 之间的点钦定 $k$ 个在以后加入的方案数。这个是一个简单的树拓扑序计数，先做一个树上背包，然后把 $(x,y)$ 这条链上挂的子树拼起来即可。

上述过程要 DP $n$ 次，状态数是 $\mathcal O(n^3)$，转移是 $\mathcal O(n^2)$，卷积可以拉格朗日插值优化到 $\mathcal O(n)$。这样复杂度是 $\mathcal O(n^5)$，应该可以过。

注意上述过程，从 $f_{j,x,d}$ 转移到 $f_{j+1,y,\ast}$ 的时候，对 $y$ 的限制是 $y\leq n-(i-j)$，只和 $i-j$ 有关，所以令 $j\leftarrow i-j$。发现上述 DP 的初值是 $f_{i-1,i,0}=1$，终值是 $\sum f_{0,x,0}$，终值是一样的。所以把 DP 转置，即把转移看成一个 DAG，等价于一个起点，问他走到所有终点的方案数之和是多少，这样只需要倒过来 DP 一次，复杂度是 $\mathcal O(n^4)$。

CF1097H Mateusz and an Infinite Sequence

CF1285F Classical?

还是太有脑子了。

首先加入所有数的约数，问题变为找两个互质的数乘积最大。

暴力可以二分莫反求出和每个数互质的最大的数。

首先根据~~观察样例~~ Hall 定理可得答案一定是 $n-1$。因为第二个联通块中选了 $k$ 个边，左侧被覆盖了的边数显然不可能少于 $k$（点减边的连通性）。

构造可以进行归纳构造。在 T2 上剥叶子 $i$，每次在 T1 上找到 $(i,fa_i)$ 路径上第一条边，然后把这个边的两端缩起来。实际意义是一个编号的替换，如果找到的边是 $(i,x)$，那删除点 $i$，对于所有 $i$ 的邻居 $k$，加入边 $(x,k)$。T2 中则可以直接删去点 $i$。拿一个树上倍增和并查集维护上述过程即可。

3.26

P11915 [PA 2025] 瞬间传送 / Teleport

难过，我咋记得讲过，但是咋还不会。

暴力是 $\mathcal O(n^4)$，所以考虑枚举操作的两个点 $(u,v)$，维护当前答案，检查能否变大。然后两个点 $(x,y)$ 不合法的条件是 $d(x,y)\geq ans$ 并且 $\min(d(x,u),d(x,v))+\min(d(y,u),d(y,v))\geq ans$。枚举 $x$ 之后，$y$ 是需要一个求交，复杂度是 $\mathcal O(n^4/w)$。

假设加的边是单向的，即只能从 $u$ 走到 $v$，从大到小枚举答案，每次加入不合法的 $d(x,y)>ans$ 的点对 $(x,y)$。可以实时维护 $f_{x,v}$ 表示对于已经加入的所有点对 $(x,y)$ 的 $\max(d(y,v))$。枚举 $x$，然后枚举 $v$。把所有的 $u$ 到 $x$ 按照距离从大到小排序，维护一个指针 $p_{x,v}$，每次删掉不合法的 $(u,v)$ 即可。

现在是双向的。但是如果 $d(x,y)>ans$，并且选了 $d(x,u)+d(v,y)\leq ans$，则一定有 $d(x,u)<d(x,v)$。因此考虑 $x,v$ 的时候，钦定他只能叉掉 $d(x,u)<d(x,v)$ 的所有 $u$。

P11927 [PA 2025] 重金属 / Heavy Metal

我怎么完蛋了。

meet in the meddle。$f_{i,j}$ 表示从起点走到 $i$，值为 $j$ 是否可行。然后从终点向前走，是 $g_{i,j}$ 表示当前边的乘积是 $j$，然后前面能拼的最大的一个数是多少。第二维只需要保留到根号级别，$g$ 的转移需要一个 dij，平衡到 $\mathcal O(n\sqrt{P\log n})$。

P11930 [PA 2025] 吃树叶 / Liście

操作是维护 $b$ 序列，支持前缀加，查询前缀内 $a_i$ 大于等于 $x$ 的位置 $b_i$ 的和。

操作强于行加列求和，显然得根号。暴力的单根号很简单，看其他题解吧。考虑 $nmz\leq 10^{16}$ 怎么用，我们希望能编一个 $\mathcal O(\sqrt{nmz})$ 的东西出来。

操作分块，每 $B$ 个修改操作分一块。这样一共会分成 $m/B$ 块。处理到第 $i$ 块的时候，需要计算 $[1,i-1]$ 的块对这之中的询问的贡献，以及第 $i$ 块内部的修改对询问的贡献。

$[1,i-1]$ 块的贡献

计算出 $f_j$ 表示处理了 $[1,i-1]$ 的块内的所有修改，此时 $j$ 的权值，这部分复杂度是 $\mathcal O(nm/B)$。查询就是一个二维数点。

总的修改次数是 $\mathcal O(nm/B)$ 级别的，而查询数只有 $z$。考虑平衡一下复杂度。

因为 $z$ 也是 $10^6$，常规分块复杂度还是有点高。所以可以分三层的块：设 $T=100$，每 $T$ 个位置分一个小块，这样一共有 $10^4$ 个小块。然后每 $T$ 个小块建立一个大块。维护每个点的值，小块内部的和，和大块内部的和，修改是 $\mathcal O(1)$，查询 $\mathcal O(T)$。

块内的贡献

一个修改操作 $(p_i,w_i)$ 对一个查询操作 $(q_j,d_j)$ 的贡献是 $[1,\min(p_i,q_j)]$ 内，$a$ 大于等于 $d_j$ 的点数 $\times w_i$，也就是 $zB$ 次数点，总点数是 $n$。这部分也是和上面一样的三层分块，只不过维护的是块内前缀和，大块内的小块前缀和，大块前缀和。修改 $\mathcal O(T)$，查询 $\mathcal O(1)$。

总复杂度是 $\mathcal O(nm/B+zT+zB+nT)$，取 $B=\sqrt{nm/z}$ 可以得到复杂度是 $\mathcal O(\sqrt{nmz}+(n+z)T)$。

CF1770H Koxia, Mahiru and Winter Festival

在最外层找两个匹配，然后剩下的往里缩就行了。

CF1815F OH NO1 (-2-3-4)

注意到可以构造一个环对三个点的贡献是 $5,4,3/5/7$ 和 $5,5,2/4/6$ 的情况。假设一个点在 $A$ 个环的第一个点，$B$ 个环的第二个点，$C$ 个环的第三个点，从前向后填，每次只考虑已经填了的和他相邻的点，和他相邻的点有 $B+2C$ 个。但是他的选择可以有 $2B+3C$ 种，所以一定是够的。

杂题选讲

讲题