额，感觉新赛季了，重新开一个写，哎虽然没啥区别。想一下怎么写，感觉开学前可以一天一天写，开学之后应该就一周一周写了，反正就是，肯定要写一点东西。

世事诡随，谨致良知。

不要想证明自己，不要试图保住什么，要以下位者的心态，虔诚看待比赛，尽力而为。

P7520 [省选联考 2021 A 卷] 支配

首先考虑支配关系的一些性质，但是当你听说过支配树之后，感觉支配树才是刻画这些性质最好的结构。

总之你发现建出支配树之后，你就非常清晰的刻画出了支配关系。考虑加入一条边只会让原本不连通的变得更连通，你发现对于 $u$ 和 $fa_u$，要么 $fa_u$ 不再支配 $u$，要么两者同时变化。

同时你发现 $u$ 变化后其子树一定全部变化，于是我们只需要找到这些 $u$ 不再被 $fa_u$ 支配的点。考虑这个限制实际上是，不经过 $fa_u$ 可以走到 $s$，并从 $t$ 不经过 $fa_u$ 能走到 $u$。

直接 $O(n^2)$ 预处理就好了，询问直接 $O(n)$ check 每个点。

CF2084E Blossom

挺好的题。

考虑对于不存在 ? 的情况如何计算答案，感觉这类题有点像是 gzy 当时讲的套娃题，你需要找到一个比较优秀的计算答案方式，然后外面套一层对于 ? 的决策。

发现计算答案可以做到 $O(n)$，枚举 $mex = i$，只需要求出 $[0,i]$ 所在位置的最大和最小值，以及找到 $i$ 的位置，分讨一下这三个位置的大小关系，即可计算 $mex = i$ 的区间数量。

考虑对于存在 ? 的情况要怎么做，此时我们继续枚举 $mex$，考虑到你需要对 ? 的位置进行决策，于是枚举一维 $c$ 表示区间 $[l,r]$ 中的 ? 数量。

记录 $w_i$ 为想要使 $mex = i$ 至少需要多少个 ?，于是贡献为

$$\sum\limits_{i = mex = 1}^n i \sum\limits_{j = w_i}^C {j \choose w_i} w_i! (C-w_i)! \sum\limits_{l,r} [c(l,r) = j \land mex(l,r) = i]$$

考虑钦定一个区间的 $mex = i$ 并不好做，我们把 $i$ 的贡献拆给每一位置，即把 $\sum$ 中的 $i$ 系数删掉，在枚举到 $i$ 的时候，所有 $mex(l,r) \ge i$ 的区间均可以贡献 $1$。

接下来我们只要能把最后面的 $\sum$ 预处理出来即可，考虑这个怎么预处理，能否直接对每个区间 $l,r$ 计算贡献，发现对于一个区间 $l,r$ 其能贡献给的 $mex$ 是一段前缀，直接枚举 $l$，移动 $r$ 的过程中维护 $mex$ 并差分算贡献即可，贡献是前缀加的形式。

P11354 [eJOI 2023] Tree Search

感觉这题应该是一个比较吃实现的题。

首先观察到 $35 = 2\log$，考虑我们能否每次把这棵树的规模缩小一半，大概是你不断跳最大的子树，直到这棵子树大小 $\le \frac{size}{2}$，去掉子树的贡献或者递归进入子树，此时我们把题目规模缩小了差不多 $\frac{1}{2}$，感觉这个就可以通过大部分数据了。

考虑点分治，每次取出分治中心，询问它的儿子，由于最多只有两个儿子，也就是这个点会把树分成三个连通块，而我们每次只会递归进去其中一个，且满足最大子树大小 $\le \frac{siz}{2}$，于是询问次数是 $2 \log$ 次。

P3546 [POI 2012] PRE-Prefixuffix

考虑一个合法的串可以被拆分成 ABSBA 的形式，我们需要的是 AB，考虑实际上是求两个相邻的 border，这个要怎么求呢。

首先考虑一个 trick，考虑我们把原串按照 $s_1,s_n,s_2,s_{n-1}\dots$ 的方式变成新串，那么新串上一个长度为偶数的回文串就是原串的 border，现在我们要在新串上找两个相邻的回文串，考虑这个题的 trick，维护每个点开头和结尾的最长回文串，然后拼一下即可。

P14830 [THUPC 2026 初赛] 回响形态

考虑上面的题的 trick，我们需要计数的是，左端点位于奇数位置，长度为偶数的回文串数量，马拉车处理一下就行了。

CF165E Compatible Numbers

发现 $a_i$ 的解集是对 $a_i$ 取反之后的一个子集，所以直接 dp 做子集和就好了。

CF1407D Discrete Centrifugal Jumps

设 $f_i$ 表示走到 $i$ 的最小次数，维护单调栈，则弹栈过程中更新答案即可。

P4747 [CERC2017] Intrinsic Interval

二轮省集课上有兴趣的为数不多的题，一直没有写，来写一下。

首先我们分析合法区间的条件是 $\max - \min = r - l$，考虑能否维护这个信息，我们可以维护 $\max - \min - (r-l)$ 的最小值。

考虑对 $r$ 扫描线，线段树维护每个 $l$ 作为左端点时区间内 $\max - \min - (r-l)$，则当 $r$ 右移时对全局 $+1$，同时我们维护单调栈，在弹栈过程中更新贡献即可。

CF1730E Maximums and Minimums

哎这题怎么都光思考怎么转化了，感觉看到因数倍数就应该想到因数个数的想法，反正考虑枚举最大值和它的因数作为最小值，找到这个东西出现的位置，然后处理一下就行了。

P16902 [CCO 2026] Melborp

这题，感觉笛卡尔树我是完全不会的，但是后面的做法其实还比较巧妙。

考虑对于一个 $i$ 分别维护 $l_i,r_i$ 表示左边和右边第一个小于该数的数，则 $b_i = (i - l_r) \times (r_i - i)$，不难发现 $b_1 = r_1 - 1$，由此可以求出 $r_1$，设为 $x$，此时 $x$ 有 $l_x = 0$，我们可以求出 $r_x$，由此可以求出若干个前缀最小值，我们对于其划分出的若干个子区间做同样的事情就好了。

哎但是好像还不会填数，不管了，感觉有点 gg。

AT_arc067_d [ARC067F] Yakiniku Restaurants

考虑如果确定了区间如何求答案，发现这 $m$ 张优惠券彼此之间独立，也就是我们需要对于每个 $j$ 找到区间内 $b_{i,j}$ 的最大值。

考虑从右向左枚举左端点，对于每个优惠券维护一个单调栈，每次考虑哪些区间的第 $j$ 张优惠券会从某个位置用到左端点上，做区间加，但是复杂度要求的很松，不需要线段树直接写差分就好了。

P4755 Beautiful Pair

后面学一下分治。

考虑分治，处理区间 $[l,r]$ 内的区间，我们找到区间最大值 $mid$，则该区间内所有区间可以分为跨过的与不跨过的，对于不跨过的部分我们可以递归子区间询问，考虑如何处理跨过的。

我们需要枚举其中一个端点，此时另一个端点的限制变成 $\le$ 某个数，这个可以主席树做询问，考虑最劣情况你枚举量还是平方的，我们在左右区间取其中较小的枚举，复杂度变为 $O(n\log n)$，带上数据结构总复杂度 $O(n\log^2 n)$。

AT_arc178_d [ARC178D] Delete Range Mex

首先你尝试观察一些性质：

• 删除顺序一定是从大到小删除，因为删除大的需要保证小的存在。
• 对于一个需要被删除的 $i$，满足 $i \notin [mi,mx]$，其中 $mi,mx$ 分别表示 $[0,i-1]$ 中位置的最小值和最大值。

考虑一个 dp 状态为 $f_{i,l,r}$ 表示加入了 $[0,i]$ 的数，这些数下标位于 $[l,r]$ 这段区间，考虑加入 $i+1$，分讨 $i+1$ 是否要被删掉。

• 需要删掉，则只能添加在区间 $l,r$ 外，$f_{i+1,l,r }\leftarrow \sum\limits_{x>l} f_{i,x,r}$，$f_{i+1,l,r} \leftarrow \sum\limits_{x
• 否则该数位置已经确定，$f_{i,l,r} \to f_{i+1,\min(p_i,l),\max(p_i,r)}$。

最后输出答案即可，但是考虑不能让原本有数的位置填数，需要分讨一些情况，另一种做法是把区间 $l,r$ 的限制修改成 $m+1$ 个空隙，后面的数需要填在哪些空隙里。

P2633 Count on a tree

树上路径第 $k$ 小，考虑序列上我们维护的是前缀主席树，我们在树上类似做法，维护根到每个点的前缀主席树，询问时差分一下即可，也就是 $u,v$ 的主席树减去 $lca$ 和 $fa_{lca}$ 的主席树。

CF1515E Phoenix and Computers

连续段 dp，我们把一段连续的开机的电脑看作连续段，设 $f_{i,j}$ 表示 $i$ 台电脑构成了 $j$ 个连续段，考虑每次启动新的电脑有三种操作：

• 新开一段，$f_{i,j} \times (j+1) \to f_{i+1,j+1}$。
• 接在某一段上，$f_{i,j}\times 2j \to f_{i+1,j},f_{i,j} \times 2j \to f_{i + 2,j}$，表示我们在这个段后面接了一个/两个。
• 合并两个连续段，$f_{i,j} \times 2(j-1) \to f_{i+2,j - 1},f_{i,j} \times (j-1) \to f_{i+3,j-1}$，表示合并时加两个选一个手动打开/加三个手动打开中间的。

然后就做完了。

P7967 [COCI 2021/2022 #2] Magneti

同样是一个连续段 dp，感觉这类 dp 的决策实际上是类似把限制全部堆到更靠后合并上来的上面，也就是在后面合并时钦定限制。

考虑设 $f_{i,j,k}$ 表示考虑了按照 $r$ 排序后的前 $i$ 个磁铁，形成了 $j$ 个连续段，这些连续段总覆盖长度为 $k$ 的方案数。

转移时依旧是考虑接在某一段左右，新开一段以及合并两段，考虑在加入一段时，我们并不需要限制其与左右边界之间的距离，只有在该段继续拼接下一个时，或者通过一块磁铁合并这两个段时，我们才限制它们之间的距离。

P9197 [JOI Open 2016] 摩天大楼 / Skyscraper

其实好像一年前就做了研究了这个题，但是不得不承认的是当时确实完全不应该做这种题，而且也没有完全搞懂？

考虑把折线拍到二维平面，我们从上往下扫的过程中加入每一段的贡献，发现每个连续段两端都会向下延伸，同时我们需要知道的是左右端点有没有确定，于是设 $f_{i,j,0/1,0/1}$ 表示前 $i$ 大的 $a_i$，形成了 $j$ 个连续段，左右端点是否确定。

转移还是考虑连续段的三种操作即可。

P5999 [CEOI 2016] kangaroo

同样可以转为排列 dp，考虑实际上要求是排列 $p$ 满足任意位置大于左右或小于左右，考虑这个限制能否用连续段 dp，从小到大插入每个数，此时只能新开段或合并两端，而不能在某一段旁边接上，于是转移即可。

P3287 [SCOI2014] 方伯伯的玉米田

最开始的想法是记录 $f_{i,j,k}$ 表示前 $i$ 个操作 $j$ 次末尾为 $k$，但你考虑转移时发现好像所有操作的一定是一段后缀，于是变成 $f_{i,j}$ 表示前 $i$ 操作 $j$ 次的最长不下降子序列长度。

考虑转移要求 $f_{k,x} \to f_{i,j},k < i,x < j,a_k + x \le a_i + j$，第一维在顺序 dp 天然满足，后两维是两个前缀，使用二维树状数组即可解决。

#22. 【UR #1】外星人

哎感觉就是，可能我确实发现了一些没啥用的性质，设计出来了一个对的状态，但是好像也没有想到该咋做。

考虑先对一个小的取模，然后对于大的取模是没有意义的，我们设 $f_{i,j}$ 表示考虑了从大到小前 $i$ 个模数，当前 $x=j$ 的方案数，转移时考虑这个数要不要起作用，若不起作用我们需要把它放在一个小模数后面，系数为 $(n-i)$，否则就是 $f_{i,j} \to f_{i + 1,j \bmod a_{i+1}}$。

感觉是，看到值域只有 $5000$ 应该要想到把值域设进状态里，所以有了一个状态，但是没有思考后面的性质。

P7502 「HMOI R1」不知道是啥的垃圾题

考虑使用 trie 树维护，一个朴素的维护方式是，我们直接根据 $x,y$ 二元组在这一位的值开节点，每个节点对应四个儿子。考虑询问时我们实际上是找一段前缀 $a\oplus x = b \oplus y$，你发现最劣情况下我们在每一层都需要递归询问两个儿子，但是实际上我们可以继续压缩信息，你发现对于一段前缀我们要求 $a\oplus x = b \oplus y$，也就是 $a\oplus b = x \oplus y$，于是我们根据 $a \oplus b$ 来开节点，每个节点维护 $x = 0/1$ 的数量，就可以进行询问，且每次询问递归的是一条链。

::::success[感觉这一次真的很对] 9.2:

感觉就是，最近可能想了很多东西，可能是因为发现时间，没那么多了，很近了，而且应该来说我还是很想要，去 WC 甚至于说去打 NOI 的吧，虽然就是，好像我并没有办法解释自己到底是为了什么而想要去，或许是想要去玩，或许是觉得去了会很开心，也可能就是，单纯的不想要回去 whk。

总之我觉得，既然想要做那就大胆去做嘛，我觉得至少，哪怕是你只是看了几篇题解，口胡了几个题，也总比说一直在抱怨或者，一直在思考没有意义的事情好。

所以，希望开学之后，不到两个月的训练能，让你恢复一下状态，甚至于说，得到一些提升吧。我觉得其实，很多事情未必那么难，未必不能去想象，但是，可能也只是想象一下，那有有啥不能想的呢，要是你真的打不进去，那我觉得确实是，太菜了，以及，确实就是过去的半年里没有很认真的在训练，没有很多提升吧，我觉得不管结果如何，也要认，以及，或许也不应该太多的，去关心别人到底是怎么样的来想你要怎么样。

9.3:

感觉，是不是，有一种很神秘的心流的感觉，可能就是，看上去好像完全，不在乎到底模拟赛打的好与坏，不在乎这个题到底，有没有做出来，或者状态好不好，就只是专注于说，这个题我思考了，然后做了，然后不会的话，那就看题解补题，然后想想为啥不会做嘛。

但是实际上好像这样，确实对心态不会有很多影响，但是其实，如果最后没有打到好的结果，其实感觉这种状态本质是，预期自己这样就会打好，本质上其实，打不好还是会更不舒服吧，但是，也没有办法了，也没有退路了，就这样吧。 ::::

9.3 dmy 模拟赛

感觉类似于是放了四个 T3 或者是一个 T2 三个 T3 这样子的模拟赛，其实还挺好的，虽然就是容易每个题都想但是都做不出来，就其实不难发现好像思考也没有很充分，后面的题基本都没有想。

T1，给你一个长度为 $n$ 的序列的划分方式，把序列划分成了 $k$ 段，一个排列 $p$ 的贡献是每段的 $\min$ 的乘积，你要求所有排列的贡献和。

首先考虑说是应该要从小到大或从大到小填数从而钦定最小值，有一个想法是设 $f_{i,j,k}$ 表示填了$[1,i]$，后两维应该是记录当前有多少区间以及多少空位，转移是考虑当前点作为一个新的 $\min$ 还是填在之前的区间，但你发现此时你无法知道每个区间需要填多少数，以及某个区间有没有用过，于是这个也无法记录到状态里，就爆了。

哎其实应该想一下的，但是可能是场上一直都没有思考说暴力去记录信息，首先你能注意到本质不同的区间只有 $O(\sqrt n)$ 种，考虑直接状压一下每个区间用了多少个，记录到状态里，还不会分析状态数，但这个是对的。

T2，感觉这个题其实，不是难题，但是确实没做出来。

额首先把最短路图建出来，考虑类似 $w_i = 1$ 的贪心去做，暴力 dfs 这张图，每个点被访问两次后就没有用了，直接跳过，否则按照字典序也就是边的编号从小到大更新后面的答案。

感觉这个是不是就是，场上做的时候其实，完全没有进行充分思考，甚至于是没有思考只有最短路上的边是有用的。感觉最应该做的就是，场上真的是四个题都要有思考的过程。

反正就是，还有一点时间，还有一些调整的时间。

T3，确实困难，等会要是会了再来看。

T4，首先考虑 $k$ 大的情况实际上只需要考虑 $k=1/2$，这个场上其实发现了这个性质，考虑如果 A 能让答案变得更大，B 显然可以通过操作相同的区间让权值不变，同理若 B 能通过操作使得权值更大，A 也会操作使得其不变。

考虑 $k=1$ 的问题实际上是简单的，只需要对增量求一个最大子段和即可。

$k=2$ 未必是简单的，你实际上是要求，操作任意一个区间之后，最大化最小子段和。

CF1580D Subsequence

问题实际上在于你可能没有办法发现哪个问题是难以解决的，也就是在做题的过程中应该要多考虑现在不会的在什么地方。

考虑难以处理的是一堆区间的 $\min$，搬到笛卡尔树上，发现一个节点的贡献就是其左右子树内选择的节点个数的乘积，于是 $\min$ 的贡献解决了，自然而然问题就好算了，是一个树形背包的形式。

以及 $O(n)$ 建笛卡尔树，考虑维护最右链，每次加入一个新的值找到其作为哪个点的右端点，并把该点原本右端点连到 $i$ 的左端点即可，代码如下：

for(int i = 1;i <= n;i++) 
{
    cin >> a[i];
    st[tp + 1] = 0;
    while(tp && a[st[tp]] > a[i]) tp--;
    ch[st[tp]][1] = i;
    ch[i][0] = st[tp + 1];
    st[++tp] = i;
}

9.4 dp

CF2238E Cake Trial

考虑把 T 看作 $-1$，F 看作 $1$，此时选择一个区间的贡献变为全局 F 的数量 $-$ 区间和。

考虑最大化这个东西实际上就是最大化最大子段和，同时我们在 dp 过程中维护当前 F 的数量，即设 $f_{i,j,k}$ 表示考虑填了前 $i$ 个位置，当前有 $j$ 个 F，以 $i$ 结尾的最大子段和为 $k$ 时的最大子段和。

CF1675G Sorting Pancakes

考虑贡献可以拆到 $i \to i+1$ 的每一段，且设原前缀和为 $s_i$，新前缀和为 $t_i$，则可以转化为 $\sum|s_i-t_i|$。

于是考虑 dp，记录前缀和以及上一位的大小，状态数看上去是 $O(n^3)$ 的，但实际上由于要求 $a_i \ge a_{i+1}$，因此第三维上界为 $\frac{m}{i}$，调和级数，转移是一段后缀。

P12558 [UOI 2024] Heroes and Monsters

这题其实遇到很多次了吧，然后感觉之前一直都只是，看懂了题解，其实都没有像现在这样想要去感受一个题的过程。

首先尝试发掘一些性质，我们尝试枚举 $k$ 求答案，发现一定是按照 $b_i$ 从小到大排序之后让前 $m$ 个怪输后面的赢，但是 dp 题你还需要搞出一些限制来帮助你转移。

考虑在我们知道了 $m$ 的情况下，限制为对于 $S$ 集合内的第 $i$ 小的英雄，满足 $a_{s_i} \ge b_i$，以及对于不在 $S$ 集合内第 $i$ 小的数 $x$ 满足 $a_x < b_{m+i}$。

我们可以 dp，设 $f_{i,j}$ 表示前 $i$ 个选出 $j$ 个在 $S$ 集合内的方案数，转移系数就是 $0/1$ 表示是否合法。

这样我们做到了 $O(n^3 + q)$，询问前缀和差分即可。

考虑能不能不每次枚举 $m$，但你发现你的限制是关于 $m$ 的，能否转化一下，考虑如果我们把限制的第二条改成不在 $S$ 集合内第 $i$ 大的 $x$，则它需要满足的变为了 $a_x < b_{n - x + 1}$，你发现这个限制不带 $m$，此时我们不需要枚举 $m$，可以分别对于前后缀求出一个 dp 数组 $f$ 和 $g$，表示前缀选一些在 $S$ 集合内的满足第一条限制，后缀选一下不在的满足第二条限制。

你发现合并两段需要满足的条件是，前缀中没有选上的一定要对应小于后缀中的怪，同理后缀中选上的要大于对应前缀中的怪。考虑找到一个位置合并两个区间，你发现找到最大的 $p$ 满足 $a_p < b_x$，则 $[1,p]$ 中所有的放到后面均会输，同时 $[p,n]$ 所有的放到前面都会赢，于是对于每个 $x$ 找到这个位置合并 $f$ 和 $g$ 即可。

P15006 [UOI 2019 II Stage] 节日

考虑 dp 的话，一个想法是对着子树结构做 dp，但是发现走的路径并不满足一定由子树走到父亲并向上，因此不能按照子树结构 dp。

考虑换到时间维做 dp，把所有询问按照时间排序，设 $f_{i}$ 表示前 $i$ 个节日，钦定必须去第 $i$ 个，最多能去几个。

考虑转移枚举一个 $j$，限制为 $t_j + dis(j,k) \le t_i$，我们尝试在 $j$ 子树内找到满足距离限制的 $f$ 最大的一个点。考虑只要我们能够枚举到 $u,v$ 路径上某一个点，就一定能取到这个最小值，从而找到合法的转移。

该如何减小枚举量呢，可以考虑点分治，每次枚举 $u$ 在点分树上所有祖先，则一定存在某个点位于两点简单路径上，且枚举量限制在了 $O(\log n)$，数据结构维护可以做到两个 $\log$。

P10440 [JOIST 2024] 环岛旅行 / Island Hopping

难以评价。

考虑从 $1$ 开始扩展，对于一个点距离从 $1$ 到 $n$ 的点中，其父亲一定是距离为 $1$ 的点，因此在父亲之前询问出的点一定是距离为 $1$ 且字典序更小的儿子，我们对于每个点这样询问，当询问到父亲就停止，由于父亲一定在儿子之前被询问到，同时每个点最多会浪费一次询问，$2N$ 次就可以解决。

9.5 dmy 模拟赛

感觉今天有点摆，其实，好像还是没有非常认真的对待一场模拟赛，有时间没有想题也没有写拍子。

T1，最开始想了做法之后去看 T2 了，过了一会回来看 T1，观察样例发现了一些特殊情况，特判了一下就好了，大概 $25$ min 的时候写了代码。

然后去做 T2，先基本把所有部分分想完了，看了看后面题，感觉这个 T4 不太像我能做的题（虽然好像只是我没有认真读懂并思考），所以决定做正解。

考虑枚举颜色之后维护连续段，然后就行了，大概 1h 的时候开始写写写，考虑了一些细节之后大概在 1.5h 写完了代码，等了一会下发了大样例，发现大样例挂了，调了很多细节问题，大概 2h 出头的时候调过了大样例。

此时其实应该写一个拍子，而且说实话这个题的拍子巨好写吧，但是最后没有写导致在边界问题出了错，但其实拍一会就能够拍出来，总之后面修改了一点细节就过了。

想了一会 T3 暴力，甚至没有读并思考 T4，想了一会发现 T3 题读的有点问题，这时候打算开摆了，想了 $m=1$ 一条链等等的部分分，然后就开摆了。

感觉这题其实，确实应该做出来，哎感觉，其实就是没有完全认真对待，感觉确实不太应该这样吧，还有，一些时间，感觉可以调整调整。

补题和题解

T1 没啥好说的，当只有一个最大值和一个最小值，且最大值要变成最小值，最小值要变成最大值，此时无法先把其余的点归位然后交换这两个，需要找一个中间量，全局取一个最小的即可。

T2 考虑每种颜色实际上会把整个序列划分成若干个连续段，而连续段之间是前后缀拼接的形式，我们维护 $f_i,g_i$ 表示从 $i$ 作为前/后缀的最长上升段，然后枚举颜色处理每一段之间关系即可，注意边界。

T3 考虑到所有非叶子节点一定在最终集合 $X$ 中，且如果定根之后我们要找的实际上是叶子中出现次数最多的一个集合 $S$ 使得 $X \in S$，答案为 $lef - cnt_S - [d_u = 1]$，即除了这种集合以外的叶子都需要修改，而根不能统计作为叶子。

然后换根 dp 一下，维护子树内集合为 $k$ 的点数即可转移，可以使用数组循环代替 dfs 节约常数。

T4 考虑一个排列实际上可以搞出来若干个置换环，而每函数操作一次相当于在环上走一步，则我们要求所有环长均为 $k$ 的因子。

考虑一个大环一定可以由若干个小环拼接出来，由此只需要考虑质因子，考虑实际上我们要用 $k_1$ 个 $p_1$，$k_2$ 个 $p_2$，$\dots$ 来拼出 $n$，对于质因子数 $m=1$ 只需要考虑是否整除，$m=2$ 可以使用 exgcd，而 $m\ge 3$ 可以同余最短路。

然后就做完了。

9.6~9.7 杂题

感觉今天没咋做题吧，哎反正最后也做了一点，补了一下昨天模拟赛。

arc。

T1，考虑本质上是最大化 A 与 C 交换次数，限制是 A 在 C 前面，考虑把所有 A 放前面取到上界，任意两个 AC 均会交换一次，于是上界为 $25^2 = 625$，考虑调整只需要交换两个 AC 即可减少一次，由于减少次数上界才 $625$，直接暴力找就行。

T2，考虑如何刻画每次操作的影响，发现能够影响的是 $a_i - 2 \times a_{i+1}$，我们只需要在某一位为 $1$ 时将这一位修改成 $1$，否则留作 $0$，则一定可以取到 $\max(a_i - 2\times a_{i+1})$ 作为下界，如果序列初始全 $0$ 则为 $0$，否则对 $1$ 取 $\max$。

T3，发现这个式子可以写成 $\frac{1}{2} \sum\limits_{i=1}^{n-1} (a_i + a_{i+1} - (a_i+a_{i+1}) \bmod 2)$，这个式子实际上只与 $a_1,a_n$ 以及任意两个之间的奇偶性相关，发现当我们确定 $a_1,a_n$ 的奇偶性时，中间部分一定是奇偶交替放最好，于是枚举 $4$ 种 $a_1,a_n$ 奇偶性，此时 $a_{1},a_n$ 一定取对应奇偶性中最大的，然后算贡献即可。

剩下的还没想清楚。

CF2252F Spectral Components

考虑 $k=1$ 时取的是虚树的带权中心，假设不在虚树的带权中心，考虑重心的性质满足最大子树大小 $< \frac{n}{2}$，于是向重心移动一步一定能够使得其子树内距离增加 $1$，子树外减少 $1$，而子树内点数显然小于子树外。

对于 $k > 1$，考虑重心一定被选进了连通块，证明同理，我们删除某个最低点，然后加入走向重心路径上的某个点，其产生贡献一定更优。

考虑选择重心之后该如何选择，发现选择一个点的贡献其实是其子树 $siz$，而由于 $siz$ 在根到子树的链一定是单调的，于是我们按照 $siz$ 从大到小选出前 $k$ 大，能够保证选出的一定是一个连通块，然后就做完了。

CF2248F Matrix Elimination

好题啊！

想一想感觉一下对于全局操作是很优的，因为对 $\sum$ 的影响非常大，考虑合法的条件是 $\sum_j a_{x,j} + \sum_{i} a_{i,y} - 3 a_{x,y} \ge 0$，而全局操作一次贡献为 $n+m-3$，考虑一个不修改的数能产生最大的增量为 $\max(n,m) - 1$，于是只要 $m+n-3 \ge max(n,m) - 1$ 就一定全局操作，发现不是全局操作当且仅当 $\min(n,m) = 1$。

于是问题转化到序列上，此时我们发现对于 $1,n$ 两个位置是有可能操作整个序列不优的，也就是需要操作 $[1,n-1]$ 或 $[2,n]$，同时发现如果同时操作这两种一定不如直接修改全局，于是只会出现其中一个。

剩下的部分应该是数学解方程。

感觉主要是你需要，找到猜想之后用式子把这个东西刻画出来，然后才能去考虑一些限制。

#17962. Exam

首先看到网格图 $n\le 20$ 就很像 meet in the middle，考虑如何统计合法方案数，我们记录 $x_{i}$ 表示路径最长前/后缀，同时记录 $y_i$ 表示路径最大子段和。

考虑恰好为 $k$ 的方案并不好计算，我们用 $\le k$ 的减去 $\le k-1$ 的，考虑如何计算 $\le k$ 的方案，发现只需要要求 $y \le k$ 且 $x_i + x_j \le k$ 即可，我们按照 $y$ 插入，插入时计数即可。

#18302. Remix

首先你发现扩大答案只能增大 $\max$ 或者缩小 $\min$，发现 $\max$ 显然是无法被扩大的，于是我们尝试缩小这个 $\min$，一个想法是说尽量找到相近的两个数作差，然后就不会了。

看题解考虑这样一个性质：对于两个子集 $C_1,C_2$，他们能够贡献出的下界为 $|S_1-S_2|$，$S$ 表示元素和，且可以达到这个下界。

考虑构造出下界只需要每次从 $C_1$ 取出元素 $X$，$C_2$ 取出 $Y$，考虑若 $X>Y$，则把 $X-Y$ 插入到 $A$，否则把 $Y-X$ 插入到 $B$，此时 $S_1-S_2$ 不变，最终能够构造出下界。

问题转化为我们需要选出一个最大值 $mx$，然后从剩下的里面选出两个子集使得其 $S_1-S_2$ 尽可能小，然后用 $mx - (S_1-S_2)$ 更新答案。

考虑值域最大值为 $mx$，则 $n$ 个元素的可重集能拼凑出的值域范围为 $[1,mx \times n]$，考虑在 $V \le 10^5$ 的情况下，$2^{22} \le 22 \times 10^5$，因此只要 $n\ge 22$，我们就可以保证存在两个子集满足 $S_1=S_2$。考虑存在重复元素怎么办，只需要把重复元素从两个集合都去掉即可。

于是我们只需要枚举所有大小不超过 $C$ 的子集，并找到差值最小值即可。

CF2246F Whoname and Unsorted Array

这题，感觉很好玩啊，哎有点厉害。

首先考虑说我们尝试在序列末尾堆出来一个 $1,2,3,\dots,n$ 来，考虑如果此时我们要把 $i$ 放后面，如果 $i$ 前面有东西，我们只需要操作 $i$ 前面的位置就可以把 $i$ 搞到后缀接上去。

考虑如果 $i$ 前面没东西，此时我们可以先随便搞一个操作把某个东西搞到 $i$ 前面来，再把 $i$ 搞到后缀里，最后操作一次后缀中 $i$ 前面的东西，就可以把多余的重新放到前面。

但这个东西只适用于序列中还有 $\ge 3$ 个无关元素，事实上我们从 $2$ 开始构造这个东西，最后后缀是 $2,3,\dots,n-1$，考虑前面的 $1,n$，若顺序是 $1,n$ 则可以直接操作，否则考虑能否调整。

尝试考虑奇偶性，考虑 $n$ 是奇数怎么办，发现我们不断选择 $2,3$ 两个位置，此时对于左右两部分分别在做循环移位，而 $n$ 为奇数时我们操作了 $n-2$ 也就是奇数次，因此能够交换 $1,n$ 的位置从而使其合法。

否则偶数情况无解，可以分析逆序对数量得出。

P16962 [SCCPC 2026] 交换余生

考虑最终序列首先可以全部除掉一个 $G = \gcd(a_1,a_2,\dots,a_n)$，接下来考虑如果存在两个 $1$ 直接就寄了，因为当你前缀取到最前面的 $1$ 出现的位置，此时前后缀 $\gcd$ 均为 $1$ 就寄了。

于是 $1$ 最多一个且放在中间，前后缀是两段 $\gcd \ne 1$ 的，考虑 $a_1,a_2$ 中必然有一个位于前缀中，我们枚举他们的质因子 $p$，考虑以 $p$ 作为前缀 $\gcd$，把所有 $p$ 的倍数全部放在前缀里，剩下的需要找到一个 $q$ 作为后缀 $\gcd$，考虑剩下的中取出两个最多只有一个放中间，于是再枚举它的因子 check 即可。

9.8 模拟赛

T1，哎看到一堆串的前缀，应该要上来就想到 trie 树的。考虑到 trie 之后就好做了，一个点能对 $j\le siz_i$ 的 $j$ 产生贡献，发现 $siz$ 每次只会在插入一个串的时候增加 $1$，那么只需要在 $siz$ 变化时更新答案就好了。

T2，首先 $O(n \log^2 n)$ 的做法是好做的，直接 cdq 分治三维偏序即可，考虑怎么做到 $1 \log$，设 $X_i = \sum_{j=1}^i r_j - b_j,Y_i = \sum_{j=1}^i r_j-y_j$，你发现当 $X_r > X_l$ 同时 $Y_r > Y_l$，此时一定可以继续扩展区间，于是只需要考虑 $l=0,X_r = X_l$ 以及 $Y_r = Y_l$ 的区间即可，树状数组可以做到 $1 \log$。

T3，还没懂。

T4，想到一个东西，但是好像不太好优化的样子，等会来写。

考虑对于每个值 $i$，维护其在序列中第一次出现的位置 $p_i$，初始化为 $inf$。我们把原序列中的位置 $i$ 变为 $i \times 2$，也就是任意两个位置中间有空隙。

考虑一次插入 $mex$ 操作此时可以转化为，选择一个值 $x$，进行操作 $p_x \to \max\limits_{i=0}^{x-1} p_i + 1$，这样我们天然保证了对于插入的 $x$，其插入时前缀中一定已经插入了 $0,1,2,\dots,x-1$，同时我们进行了 $+1$，从而保证两个插入 $mex$ 操作不在同一个时间。

于是我们能保证插入的一个数一定是当时序列的 $mex$，且不存在两个不同的数作为 $mex$ 被同时插入。

此时我们刻画出了每个数被插入序列的时间，考虑如何处理询问，实际上我们要找到在进行不超过 $k$ 次操作的前提下，最大的值 $i$ 满足 $\max\limits_{j = 0} ^ {i} p_i \le m$，这里的 $m$ 和 $p_i$ 均没有进行上文提到的 $i \to i \times 2$，所以可能最后一个插入的合法的 $mex$ 的 $p$ 会变成 $m+1$，细节还没想好怎么处理。

于是我们可以 dp，设 $f_{i,j,k}$ 表示在 $p$ 序列考虑了前 $i$ 个位置，进行了 $\le j$ 次操作，当前 $p$ 序列前缀最大值为 $k$ 是否可行，发现 $0/1$ 随着 $k$ 是单调的，我们改为记录 $f_{i,j}$ 表示 $p$ 序列前 $i$ 个位置，进行 $\le j$ 次操作，可能的前缀 $\max$ 的最小值。

转移是简单的，讨论 $i+1$ 的位置要不要进行操作，若进行操作则 $\min(f_{i,j} + 1,p_{i+1}) \to f_{i+1,j+1}$，不操作则 $\max(f_{i,j},p_{i+1}) \to f_{i+1,j}$，这里需要优化，但是我暂时还不会，也可能这个东西确实没法优化。

处理询问，发现对于同一个 $k$，$f$ 值随着 $i$ 单调不增，于是我们对于询问的 $k$ 二分最大的 $i$ 满足 $f_{i,k} \le m$，则 $i + 1$ 为询问的 $mex$。

这个目前也只会暴力，可能在优化 dp 的过程中可以用离线整体二分或者某些处理方法来做询问，也可能确实做不了。

正解

首先场上你发现了一个性质是操作一定是最后 $k$ 个位置，考虑最终 $mex$ 一定是原序列的某个前缀中没有出现的数，记录这些前缀未出现数的序列为 $b$。

我们尝试维护从 $i$ 位置开始每次都操作的 $mex$ 序列，按照从大到小扫描询问的 $m - k + 1$，每次加入一个位置考虑其影响，设 $f_i = mex(f_{i - 1},a_i)$，找到该位置后面第一个满足 $f_{i - 1} = a_i$ 的位置 $p$，则我们在该位置前面加入一次操作没有用，同理对于后面的所有的也没有用，于是有用的只有 $[i,p)$，发现贡献是把这些位置的值变为 $b$ 序列的下一个值，每次做区间 $+1$。

9.9 杂题

哎怎么说，一上午效率好低啊，就研究了一个题，但是最起码研究明白了吧，然后会了昨天模拟赛 T4。

P14364 [CSP-S 2025] 员工招聘

dp 贡献的延迟决策，可能写的有点绕，但是感觉我可能就是这样理解明白的。

怎么叫延迟决策呢，考虑最终我们要怎么算方案数，对于一个方案假设最终拒绝了 $x$ 个人，则对于 $c_i > x$ 的 $cnt$ 个人是不区分的，这些人可以任意排列，方案数为 $cnt!$。

其实相当于我们把 $c_i \le x$ 的人全都已经填进了序列，并且计算了方案数，而对于 $c_i > x$ 的人我们为他们在序列中空出了一些位置，把这些人填进每个位置即可，方案数就是排列数。

于是在决策的过程中我们可以时刻把所有人划分为两个集合 $S_1,S_2$，假设当前已经决策了 $j$ 个人失败，集合 $S_1$ 中的人 $p$ 满足 $c_p \le j$，集合 $S_2$ 中的人满足 $c_p > j$，且我们已经对 $S_1$ 集合中的人计算了方案数，而没有对 $S_2$ 中的人计算方案数。

由于前缀中失败的人数是单调不降的，因此人只会从集合 $S_2$ 变为集合 $S_1$，而不会从 $S_1$ 重新变回 $S_2$，于是我们可以在一个人从 $S_2$ 变为 $S_1$ 时把它填到前面预留的空位里，计算方案数。

考虑一个从前向后决策的过程需要记录哪些信息，当前失败的人数 $j$，以及当前预留了 $k$ 个空位给 $S_2$ 集合中的数，于是设 $f_{i,j,k}$ 表示考虑了前 $i$ 天，当前有 $j$ 个人失败了，前 $i$ 天中预留了 $k$ 个空位给当前仍满足 $c_p > j$ 的 $p$，$S_1$ 集合的方案数。

考虑最终 $S_2$ 集合所有数均满足 $c_i > x$，于是答案实际上就是 $S_1$ 集合方案数乘上 $S_2$ 集合的排列数，由于我们在一个人从 $S_1\to S_2$ 的时候计算贡献，于是 dp 中最终只计算了 $S_1$ 集合的方案数。

考虑转移，转移时我们需要决策第 $i$ 位要填一个 $S_1$ 中的数还是预留一个空位，同时对于 $j$ 变大时，我们需要把当前 $c_p = j$ 的从 $S_2$ 加入到 $S_1$ 计算方案。考虑其中的一些填入到了前面的空位中，剩下的将会填到后面的格子中。

令 $a_i = \sum\limits_j [c_j = i],b_i = \sum\limits_{j \le i} a_j$，即 $a_i$ 表示 $c_p = i$ 的 $p$ 的数量，$b_i$ 表示 $c_p \le i$ 的 $p$ 的数量。

若 $s_{i+1} = 0$，此时该位置无论填什么都必然会增加一个失败的人，于是 $j \to j+1$。我们先来计算 $c_p = j+1$ 的 $p$ 的贡献，枚举 $t$ 表示有 $t$ 个 $c_p = j+1$ 的 $p$ 放置在了 $pos \le i$ 预留的空位中，剩余的放在后面的格子里。

这部分方案数为 ${a_{j+1} \choose t} {k \choose t} t!$，即选出 $t$ 个 $c_p = j+1$ 的 $p$，并从 $k$ 个空位选出 $t$ 个填进去的方案。

• 若该位置放一个空位，有转移 $${a_{j+1} \choose t} {k \choose t} t! f_{i,j,k} \to f_{i+1,j+1,k-t+1}$$
• 若该位置放一个 $c_p \le j+1$ 的 $p$，考虑选出这个 $p$ 的方案数为 $b_{j+1} - (i - (k-t))$，于是有转移 $${a_{j+1} \choose t} {k \choose t} t! (b_{j+1} - i + k - t)f_{i,j,k} \to f_{i+1,j+1,k - t}$$

若 $s_{i+1} = 1$，若填一个 $c_p \le j$ 的数 $p$，此时同样会使得 $j \to j+1$，于是选出这个数的方案数为 $b_{j} - i + k$。同样枚举 $t$ 表示有 $t$ 个 $c_p = j+1$ 的 $p$ 放置在了 $pos \le i$ 预留的空位，有转移

$$ (b_{j} - i + k){a_{j+1} \choose t}{k\choose t} t! f_{i,j,k} \to f_{i+1,j+1,k - t}$$

否则预留一个空位给 $c_p > j$ 的人，$j$ 不变，$k+1$，即

$$f_{i,j,k} \to f_{i+1,j,k+1}$$

要求通过人数 $\ge m$，也就是失败人数 $\le n - m$，枚举失败人数 $x$，由于是最终状态，我们要求 $S_2$ 中只有 $c_p > x$ 的 $p$，于是最终答案为 $\sum\limits_{j=0}^{n-m} f_{n,j,n - b_j} \times (n-b_j)!$。

时间复杂度 $O(n^3)$。

打了一场 edu，感觉自己菜完了。

A B 都没啥好说的。

C，令 $S = x + y$，考虑任意时刻均满足 $x+y = S$，而对于 $a+b = S$，有 $a+b = a \oplus b + 2 \times (a \& b)$，我们希望最大化异或，也就是最小化 $a \& b$，考虑只需要满足 $a \le x$ 且 $a$ 是 $S$ 的一个子集即可。

D，一上来看样例猜测答案最多 $3$，尝试构造发现是合法的，只需要把值域限制在 $[-2,2]$ 即可，对于一段连续的 + 或 - 可以在 $1,2$ 交替，但是上来 $ans = 1$ 判错了导致调了特别久，最后改成了 dp。

F，考虑最终答案的形态，一定是 $3$ 是一个连通子图，而对于 $1$ 图的所有连边 $u,v$ 均在 $2$ 上连通。我们找到一棵生成树作为 $3$，发现下一个条件实际上是能找到一个不包含生成树边的环，由于 $m \le n + 9$，于是只有 $10$ 条边不在树上，我们 $2^{10}$ 枚举用哪些边替换树边，并 check 能不能搞出来一个环就行了。

哎，有点极限过题。

CF2152G Query Jungle

首先考虑静态的做法，发现一个点有贡献当且仅当其子树内没有其它关键点。考虑如何动态的维护这个东西。

感觉想不出来实际上就是，没有想到怎么用 dfn 或者这类东西来刻画出这个限制，考虑这样刻画，设 $nxt_i$ 表示 $dfn_u > dfn_i$ 的最小的 $u$，则限制要求 $dfn_u > dfn_i + siz_i - 1$，考虑在 $dfn$ 开线段树，维护每个区间最前和最后的黑点，以及区间内答案，合并时考虑前面区间的最后一个与后面区间的第一个是否合法即可。

对白点同样维护即可做翻转操作，时间复杂度 $O(n \log n)$。

CF2239C Revival

哎这题，感觉比上面那个难啊。

考虑倒着做，此时根据后缀中确定的信息，我们可以得到前缀中出现的数字的集合，考虑按照相邻两个 $s_i,s_j$ 和中间的 $p$ 来确定 $s_j$。

考虑 $s_j - s_j$ 的贡献是如何带来的，你发现如果你能枚举 $p_r$，那么 $p_1,p_2,\dots,p_l$ 的集合你是知道的，而你并不关心他们到底如何排列，于是考虑二分 $p_r$，然后直接求出贡献与 $s_r - s_l$ 比较即可。

复杂度 $O(n\log^2 n)$。

P8321 『JROI-4』沈阳大街 2

这个就是，上面一样的套路吧，两个序列一起排序，钦定在后面产生贡献，同时由于我们可以根据其中一个的匹配情况求出另一个，因此只需要记录 $f_{i,j}$ 表示前 $i$ 个，A 序列还有 $j$ 个未匹配，然后考虑下一个要不要匹配即可。

复杂度 $O(n^2)$。

9.10 模拟赛？

好困，哎，感觉前两个题也，不像是我会做的类型，就可能属于见过就会的类型吧。

AT_arc207_a [ARC207A] Affinity for Artifacts

之前已经写了匹配的做法，考虑一下 dp 延迟钦定怎么做。

我们先假设每次 $x \to x-1$ 都能被完美利用，此时花费是最优的，用 $X$ 减去这个花费得到的就是能够浪费的节约次数，也就是无效操作的次数。

考虑对于一个 $i$，所有没有在 $[1,i]$ 匹配的 $a_p \le i$ 的物品都会浪费 $1$，考虑设 $f_{i,j,k}$ 表示考虑前 $i$ 次删除的灯，当前有 $j$ 个 $a_p \le i$ 的未匹配，浪费的次数为 $k$ 的方案数，考虑如何转移。

令 $b_i$ 表示 $\sum_p [a_p = i]$，$s_i = \sum_{j = 0}^i b_j$。

分类讨论 $i+1$ 填的是 $\le i+1$ 还是 $> i+1$，填 $> i+1$ 相当于留出空位，同时枚举 $t$ 表示有多少个 $a_p = i+1$ 的物品放入了前面预留的空格中，这部分方案数为 ${b_{i+1} \choose t} {i+1-(s_{i+1} - j) \choose t} t!$，注意第二个组合数中是 $i$ 或者 $i+1$ 取决于这一位填的是 $\le i+1$ 还是 $> i+1$，然后就能转移了。

P2519 [HAOI2011] problem a

本质缺乏判断一个做法是不是正确的能力，或者就是你想出来一个东西，想不到一些错误的情况，想不到如何验证你的做法对或者不对。

考虑每次给出的限制实际上是排序后某一段区间 $l,r$ 内均相等且不与 $l-1,r+1$ 相等，于是区间有交但不相等是不合法的。

考虑对于完全相同的 $k$ 个区间 $l,r$，其最多真话的人数为 $\min(k,r-l+1)$，我们需要选出一些不交的区间使得其权值和最大，考虑 dp，设 $f_i$ 表示考虑到前 $i$ 个位置，最大的贡献，转移时若 $i$ 为某个区间右端点则 $f_{i} = \max(f_l + val)$。

P4099 [HEOI2013] SAO

考虑各个子树之间是独立的，考虑把 $v$ 合并到 $u$ 上的过程，假设 $u < v$，我们需要知道 $u,v$ 前面分别有多少点，才能够求出合并这两个毫不相关的序列的方案数。

于是记录 $f_{i,j}$ 表示考虑 $i$ 子树 $i$ 的拓扑序为 $j$ 的方案数，合并时枚举 $v$ 的哪一段前缀合并到 $u$ 前面，剩下的合并到 $u$ 后面，朴素转移时 $O(n^3)$ 的，发现对于同一段前缀合法的 $j$ 是一段前/后缀，于是前缀和优化，树上背包复杂度可以分析到 $O(n^2)$。

感觉，摆就摆了，哎也没必要，有太大负担或者啥吧，就反正也没有真的摆，就是睡一会然后活动一会，我觉得多一个题少一个题，其实，没有很大的影响吧。毕竟说实话可能，也不会因为多做或者少做一个题就，但是，哎，谁知道呢。

模拟赛

感觉没打也没那么想要补题，就，随便说一说看一看吧，其实也不难。

T1，你首先发现如果暴力枚举 $O(n^2)$ 个数显然数量级是没法做的，考虑暴力是我们枚举之后枚举它的因子，于是我们反过来枚举 $\le \sqrt {2\times10^9}$ 的所有数 $p$，考虑找到 $a_i \bmod p = a_j \bmod p$，统计这些数对就好了。

T2，哎考虑 $i$ 和 $i+k +1$ 显然是不交的，每个 $l$ 可能对应的右端点 $r$ 只可能是 $[l-k,l+k]$，考虑说我们只保留 $1,1+2k+1,1+2(2k+1) \dots$ 这些点，询问时二分出前后最靠近的位置，然后暴力扫描这些位置对应的 $4k$ 条线段统计答案即可。

T3，考虑从小到大加入一些区间的过程，发现只有当某个区间加入后当前连续段被扩大这些区间才有意义，我们把每个区间严格包含的区间取出来，连成一棵树，则实际上我们要求一个树的 topu 序。

考虑对这个过程 dp，设 $f_{l,r}$ 表示当前连续段为 $[l,r]$ 的方案数，考虑加入一个区间的时候计算其对 topu 序的贡献，暴力复杂度 $O(n^3)$。

考虑扩展时对于一个 $l,r$ 分别贡献是前后缀，直接前后缀优化即可。

9.12 模拟赛

哎，这场题搬简单了啊。

T1，首先注意到翻转区间只影响 $x,y$ 均在区间内的贡献，因此我们只要预处理每个区间逆序对数即可，设 $f_{l,r}$ 表示 $[l,r]$ 逆序对，转移有 $f_{l,r} = f_{l+1,r} + f_{l,r-1} - f_{l+1,r-1} + [a_l > a_r]$，然后 $O(n^2)$ 枚举区间即可。

T2，首先你需要读题，意识到 $a_i$ 单调。

考虑合法限制是 $\forall i,a_i \le i$，因为单调，若存在 $a_i > i$，由于数只能增大无法变小，能变成 $[1,i]$ 的只有最多 $i - 1$ 个数，于是无解。

否则一定有解，考虑以 $a_i = i$ 的部分划分成若干段，对于每一段 $l,r$，我们让 $a_l$ 从 $l$ 一直变到 $r$，同时保证 $a_{l+1} = a_l$，在 $l$ 增加过程中处理剩下的数，使其变为 $i-1$ 即可。

T3，本来想写个暴力就走，结果会了，最后扫描线把区间排序之后答案存错位置了，怎么还过了 loj 和大样例。。。

首先考虑 $O(nq)$ 怎么做，树形 dp，考虑设 $f_{u,0/1/2/3}$ 表示考虑 $u$ 子树，对周围点无限制/儿子必须 0/父亲必须 0/自己 0，转移一下就行，发现统计答案是深度 $\le d$ 的点直接取 $\max(a,b)$，深度 $=d$ 的部分取 $\max(f_{0/1/2/3})$。

过了一会发现这 dp 没必要每次做一遍，然后就做完了。

T4，首先你发现操作顺序与最终答案无关，考虑枚举上下左右四个方向各移动多少，复杂度 $O(r^2c^2)$。

考虑只枚举上下，则形成了若干条竖着的线段，左右方向可以直接求出来，复杂度 $O(r^2n)$。

考虑一定存在某个操作恰好覆盖上下界，枚举量变成 $O(n^2)$，总复杂度 $O(n^3)$。

诶但是真的吗，好像我写的是错的，理解的是错的，哎不懂啊。P14382 [JOISC 2017] 开荒者 / Cultivation。

9.13 打 CS 就不写了，没咋想题，可能想了一个题明天再写吧。

9.14 杂题

P16968 [SCCPC 2026] 博德之跃 3

wssb。

考虑什么情况要用 $3$，首先不能用 $3$ 的时候直接取两端最小值，否则考虑怎么用，找到下一个与当前字符不同的位置，若左右都更小，则我们希望尽可能少放当前字符，设左右长度分别为 $ll,lr$，则我们先进行 $\min(ll,lr)$ 次 $3$ 操作，然后进入子问题即可。

否则若两端都大，我们希望尽可能多的放当前字符，先把 $ll+lr$ 个全放进去，再做子问题即可。

否则我们想要尽可能早点把小的放进去，并且另一端希望尽可能晚的放大的，于是只从一端放进去即可。

一定要注意 $ABA^R$ 放的是 $A$ 不是 $AA^R$ 啊。

#18727. Invention of Saruca

wssb？

额，首先其实不太应该上来直接想如何构造，你首先要发现题目限制非常死，要求必须 $2,3,\dots,n$ 都出现，于是只能是最开始 $2$ 个数，然后每次这个数替换为右边集合中两个数，再从这两个数里面选一个继续替换。

考虑建一棵每个点右子树大小为 $1$ 的二叉树，每次操作变成把一个 $u$ 替换为两个儿子，并递归替换左儿子，从下往上构造，令 $a_u = a_{ls} + a_{rs}$，但这样实际上会有一点问题，主要问题在于不能重复，而我们这样只有 $2n-1$ 个数，最后一个数需要等于 $sum - a_1 - a_2 - a_3$，这个数不能出现过。

你发现实际上就是要求 $a_1,a_2,a_3$ 里面不出现，而 $a_2$ 显然不会出现，于是只需要保证 $a_1,a_3$ 不出现即可，值域给的很宽泛，直接暴力找合法数就可以。

$n\le 3$ 需要特殊处理。

#17957. RPS Bubble Sort

先考虑两种颜色的情况，设为 $1,2$，进行 $t$ 次操作后原序列中位于 $i$ 的 $1$ 的位置为 $\max(i-t,k)$，其中 $k$ 表示该位置是第 $k$ 个 $1$。

后面挺难想，考虑把三种转成两种，你发现按照极长只有两种字符的前缀分段，每次操作各个段之间是独立的，不会产生位置交换，那么我们只需要把序列分成若干段，每段内均为两种颜色的情况，然后就做完了。

感觉，一上午做两三个题，哎虽然效率确实挺低的，但是哎，怎么说，反正最起码自己思考自己做了，有点思考的过程。

9.15 模拟赛

T1，都说感觉很难，感觉其实还好，做了十几分钟。

考虑最开始把相邻相等的先删掉，因为最后总要删，而且单出来的与你删哪一对是无关的，最后得到一个不存在相邻位置相等的串。

先考虑 01 交替的串怎么做，发现只能是翻转前一半，需要满足前一半与后一半相等。考虑能否扩展到字符集大小 $26$，你发现有些情况不一定前后完全相等但也能消掉，分析一下发现我们可以先贪心把最外层能匹配的匹配掉，则要求里面的一定能删空，于是里面的要求是前一半和后一半相等，然后就做完了。

T2，考虑最终会有一个点没有被染色，我们把这个点作为根，则要求每个位置必须被父亲那条边染色。考虑 $v \in son_u$，若 $p_v < p_u$ 则该条边无限制，否则该条边必须晚于父亲那条边。

发现构成了一棵有向树，而我们要求的实际上是它的 topu 序，于是只需要维护 $siz$ 即可。考虑如何换根，维护当前从父亲过来的子树大小，维护当前的 $\sum\limits_{rt = u} \prod\limits_v \frac{1}{siz_v}$，最后乘上 $(n-1)!$ 即可。

后两题还不会，后面写。

T4，我们首先需要选择一个计数对象，你发现如果只是对 $(l,r,m)$ 的三元组计数是可能算重的，于是你考虑对 $m$ 做扫描线，把每个区间放在最后一个 $m$ 上统计。

考虑合法的区间是什么样的，我们记录 $x_i,y_i$ 分别表示 $m$ 左边最后一个和右边第一个 $a_p = i$ 的 $p$，首先若存在 $x_a < x_b$ 且 $y_a < y_b$，则 $[y_a,y_b]$ 之间不存在合法的 $r$。

否则考虑对于每个 $r$ 合法 $l$ 的数量，考虑找到 $y_p < r$ 的颜色 $p$，这些颜色都在 $[l,r]$ 出现过，于是 $l$ 的最大值为所有 $x_p$ 的 $\min$，同时 $l$ 的最小值为所有 $y_p > r$ 的 $x_p$ 的 $\max + 1$，以及我们要求 $nxt_m > r$ 从而保证 $m$ 是最右边的分界点。

9.16 杂杂杂杂杂杂杂杂题，哦原来是构造

P4786 [BalkanOI 2018] Election

牛。

题意是给定 $1,-1$ 序列，最小化删除次数使得任意前后缀和 $\ge 0$。

先考虑一个贪心是你从前往后扫，当当前前缀和 $<0$ 时删掉当前位置的 T，由于我们每次删除都是在最右边删除，能够最大化对于后缀和的贡献，因此贪心策略是对的，暴力复杂度 $O(nq)$。

考虑这个过程实际上是找到 $pre_p = -1,-2,-3 ,\dots$ 这些位置删掉，因此对于前缀操作次数为 $-\min pre_p$，考虑每个 $p$ 会对 $[1,p]$ 的后缀和产生影响，我们记 $suf_p$ 表示进行完前缀的操作之后的后缀和，如何统计前缀操作对每个位置的贡献，你发现所有操作中没有对 $p$ 产生影响的是 $-\min\limits_{q < p} pre_q$ 次，最终答案为 $-pre_{\min} - suf_{\min}$，$suf_i = lst_i + pre_{p < i} - pre_{\min}$，于是最终只需要最小化 $p

相当于选出前后缀最小化和，等价于总和 - 最大子段和，线段树维护即可。

CF2025F Choose Your Queries

哎，这么厉害。

首先对于这种二选一的操作考虑建图，发现对于任意两个连通块之间贡献互不影响，于是对于每个连通块计算答案。

对于构造最优化解的问题，一个想法是可以尝试找到解的下界，每条边能产生 $1$ 的贡献给 $u$ 或 $v$，答案为 $\sum val_u \bmod 2$，该答案下界为 $(\sum val_u) \bmod 2$，即边数 $m \bmod 2$。

尝试建出 dfs 树，每条边的决策在深度较小的点上考虑，当我们决策挂在 $u$ 上的所有边时，我们先暂时不关心 $u$ 的贡献，而是让所有 $u \to v$ 的 $v$ 贡献均为偶数，这是容易做到的，只需要判断 $v$ 当前贡献并决策这条边贡献给 $u$ 还是给 $v$ 即可，于是最终只有根可能贡献为 $1$，此时我们做到了下界 $m \bmod 2$，于是这样构造即可。

9.17 模拟赛

睡觉了，但确实，我应该一个题也不会。

T1，不知道怎么样考虑到的，考虑设 $x_i$ 表示 $i$ 作为起点操作的次数，则有 $a_i = \sum\limits_{i-k < j \le i} x_j$，差分一下有 $a_i - a_{i-1} = x_i - x_{i-k}$，考虑我们搞出若干个环，先钦定任意一个位置 $x_i = 0$ 求出整个环的每个位置的值，此时若存在某个位置 $<0$ 则我们给整个环做加法使得最小值 $= 0$。

现在我们已经找到了一种操作次数使得所有点操作次数非负且最终所有数相等，但该操作并不一定能够满足所有数最终均为 $0$，考虑只要确定下任意一个 $a$，剩余部分均会被确定，于是我们考虑 $a_0$ 的位置，你发现修改一个 $x$ 会修改一整个环，我们考虑每个环修改一次的代价，然后考虑修改哪个环代价最小，修改这个环使得 $a_0$ 最终变为 $0$ 即可。

T2，首先观察我们能够向后加哪些串，你发现对于加的这些串中只有最小的循环周期与它的若干倍之间会算重，比如 aabaabaa 中，baa 可能与 baabaa 算重，而其他不会，这个是能够证明的。

考虑把所有倍数串用这个串替代，假如最多能重复 $a$ 次，其余的不重复的串有 $b$ 个。考虑每个本质不同的串，拼出它的次数实际上都是一段区间，我们要求出的实际上就是区间包含 $k$ 的区间个数。

考虑用左端点 $\le k$ 的减去右端点 $baabaa 的串被算作 $2\times$baa。

对于一些连续的 baa，其最多能连续放 $a$ 个，因此我们把每次看作三种：

• 放置 $a$ 个 baa。
• 放置 $b$ 个串中的一个。
• 放置 $x < a$ 个 baa，为了去重该位置后面只能直接结束或者接上 $b$ 个串中的一个。

于是有 $f_{i,0/1}$ 表示 $i$ 次操作，最后一个是否为 $1$。

转移有 $f_{i,1} = (a-1)f_{i-1,0},f_{i,0} = bf_{i-1,1} + (b+1) f_{i-1,0}$，最终答案为 $\sum_i f_{i,0} + f_{i,1}$，可以矩阵乘法优化，复杂度 $O(n+q\log n)$。

9.19

初赛了，哎，84，没啥好说的，菜。反正过了就行，无所谓了。

9.20

P3643 [APIO2016] 划艇

题也不难，为啥就是没做出来呢？感觉本质就是，没把需要做的问题刻画出来，然后导致不知道在想啥。

考虑一个暴力 dp 是你设 $f_{i,j}$ 表示前 $i$ 个，第 $i$ 个派出了 $j$ 只船的合法方案数，转移枚举上一个状态暴力转移，但这样复杂度是带值域的，显然没法过。

考虑能否离散化，修改状态为第 $i$ 个位于第 $j$ 个区间，此时的转移相当于是，我们需要把 $(k,i]$ 中的所有学校，派出的船数量均位于第 $j$ 个区间，且构成上升序列的方案数。

考虑 $n$ 个数从 $[0,L]$ 选构成上升序列的方案数为 $L+n\choose n$，相当于加入 $n$ 个 $0$，选择了第 $i$ 个 $0$ 则表示 $i$ 位置选了 $0$，否则从小到大第 $k$ 个元素表示非 $0$ 的第 $k$ 个人选择的值，这样就计算出了方案数，于是我们只需求出 $(k,i]$ 中可以位于区间 $j$ 内学校数量 $m$ 即可。

最后前缀和优化一下复杂度 $O(n^3)$。

原来今天有模拟赛，感觉其实现在已经很清楚了，太难的题确实不太可能苛求能去做出来，更应该做的应该是去提高前两题速度和稳定性，以及代码能力，留出更多时间来放给后面，哎，日子其实不多了。

T1，首先有一个无脑矩形面积并做法，直接维护区间和，区间赋值，区间最大值及位置，然后考虑加入一个东西的时候与后面的交即可。

事实上可以做到线性，发现当 $i + d_i > j + d_j$ 时，$i$ 三角形会被 $j$ 覆盖掉一部分，我们使用单调栈维护当前有贡献的三角形，当某个位置被覆盖掉，也就是弹栈的过程，我们就将其贡献删除，最后加入贡献，时间复杂度 $O(n)$。

T2，首先答案有上界 $2n$，考虑如果找到了最终停下的位置，则该位置之后的每一段都会被经过两次，该位置之前的会经过 $1$ 次或 $3$ 次，其中一段经过一次的限制为前缀中补给数量 $>$ 监测点数量，于是枚举答案点算贡献即可。

T3，考虑从后往前贪心，二分哈希暴力判断即可。

9.21 真的是杂题

AT_agc032_d [AGC032D] Rotation Sort

排列的题，当遇到这种变化的东西，可以尝试研究不变的东西的性质并尝试对着这个东西做。比如这题中你发现不变的部分一定是一个上升的子序列，考虑对着这个 dp。

我们设 $f_{i,j}$ 表示考虑把前 $i$ 个数相对顺序排好，其中当前不变的子序列最后一个数为 $j$ 的最小代价，考虑如何转移，讨论 $a_i$ 与 $j$ 的大小：

• $a_i < j$，此时只能把 $i$ 向左移动，有转移 $f_{i-1,j} + B \to f_{i,j}$。
• $a_i > j$，事实上此时 $i$ 有很多选择，可能向左移动，可能向右移动，也可能不移动，但我们只需要考虑不移动和向右移动两种情况。

对于不移动，有 $f_{i-1,j} \to f_{i,a_i}$，对于移动则有 $f_{i-1,j} \to f_{i,j} + A$，而为什么不需要考虑向左移动呢，你发现对于向左移动的情况，一定存在一个 $k$ 使得 $k > i$，且我们会在 $f_{i-1,k}$ 时强制 $i$ 向左移动，于是所有合法情况均会被扫描到，不需要在这里转移。

复杂度 $O(n^2)$。

#18488. Stones 1

首先你不难发现对于一个极长颜色相同连续段，只有一个数能产生贡献，由于这题只需要最大化贡献，不妨只保留最大值，此时序列变为一个黑白交替的序列。

考虑这样的结论，我们从除了端点以外的部分中选出任意的 $\lceil \frac{n - 2}{2} \rceil$ 个，一定存在方案使得我们能取出这些数。

只需要考虑每次找到选中与未选中相邻的一个选中区间，将该区间删掉，并把左右两个合并，若存在一个有标记则打上标记。

于是排序后从大到小取即可。

18298. Monochrome Tree

一个想法是从叶子开始选，直到选不了了此时会出现有贡献的对，而我们希望贡献尽可能小，所以找子树大小最小的点选，考虑说明这是对的。

首先显然一个黑点 $u$ 子树内应该全部为黑点，因若存在 $u,v$ 满足 $u$ 是 $v$ 祖先且 $u$ 为黑色而 $v$ 为白色，则交换显然不劣，贡献到的点对只会更少。

同时选 $u$ 子树贡献为 $siz - 1$，于是从小到大贪心即可。

CF1913F Palindromic Problem

我们考虑一次操作的贡献，这里假设修改成与原来不同的字符。原本不以该位置中心的包含该位置的回文串均会不合法，而新变得合法的部分实际上就是某个回文中心 $x$，设其修改前回文半径为 $r$，考虑把 $s_{x-r}$ 修改为 $s_{x+r}$，此时增加的回文串是前缀 $x - r$ 与后缀 $x+r$ 的 lcp 长度。

考虑新增的贡献是好处理的，直接记录 $f_{i,j}$ 表示 $s_i$ 修改成 $j$ 的增加量，对于减少量实际上是对于每个中心 $i$ 的一次函数形式，可以差分解决。

构造方案，变小 < 不变 < 变大，从前往后或从后往前扫描即可。

CF2233E2 Permutation Transmission (Difficult Version)

一个性质是说，对于两个 $1$ 数量相同的串可以任意排列，如果你知道了这个结论，显然你不难发现每一位的 $1$ 的数量是确定的，只需要把相同的排列数算一下乘起来就好了。

感觉写代码还是太烂了，哎，确实应该认真写代码了，后面多写一写。

P3809 【模板】后缀排序

第一百万遍学 SA。

感觉其实没啥好说的啊，好像其实我在一百万遍之前就已经懂了 SA 在干啥，但这东西半年不写真的很容易忘吧。

如何用 SA 求 lcp，考虑记录 $h_i$ 表示排名为 $i$ 与排名为 $i+1$ 的后缀的 lcp，则有后缀 $x,y$ 的 lcp 应该为 $\min\limits_{i=rk_x}^{rk_y - 1} h_i$，考虑如何求出 $h_i$，有结论原串中相邻位置 $i,i+1$，满足 $h_{rk_{i+1}} \ge h_{rk_i} - 1$，于是按照原串顺序记录一个 $x$ 可以做到 $O(n)$ 预处理 $h$，使用 st 表可以做到 $O(n\log n)$ 预处理 $O(1)$ 询问。

给定字符串 s，求本质不同子串数量。

考虑子串转化为后缀的前缀，你发现对于排序后，假如已经加入了前 $i-1$ 个串，现在要加入第 $i$ 个，其与上一个串 lcp 的前缀显然已经加入过，而后面的均未加入过，也就是加入的数量实际上是 $len_i - h_i$，于是直接求就行了。

要注意 SA 在求 $h$ 数组过程中,如果 $h_i$ 表示排名 $i,i+1$ 的 lcp，是可能在过程中访问到越界的，也就是你做到 $i$ 的时候访问到 $rk_{i+1} = 0$，而改成 $i,i-1$ 就没有这个问题。

CF1946F Nobody is needed

若不进行区间询问而是全局询问，可以通过 dp 来解决，考虑设 $f_i$ 表示 $i$ 结尾的上升序列数量，考虑转移实际上是枚举因数 $j$ 从 $f_j$ 转移过来，单次复杂度 $O(n \log n)$。

考虑此时我们需要进行区间询问，当固定 $l$ 可以通过 $O(n\log n)$ 的 dp 算出，复杂度 $O(n^2\log n)$，考虑如何优化，对 $l$ 做扫描线，考虑加入一个 $l$ 的贡献，你发现实际上是找到所有倍数，它能够给每个倍数增加 $1$ 的贡献，于是我们枚举倍数，并对每个倍数把贡献重新加给他们的倍数，倍数是 $O(\log n)$ 的级别，于是这部分复杂度 $O(n\log^2 n)$，考虑我们需要在 $f$ 数组上贡献增量，一共 $O(\log n)$ 个倍数，单点修复杂度 $O(\log n)$，总复杂度 $O(n\log^2 n + q\log n)$。

9.22 模拟赛

P12651 [KOI 2024 Round 2] 最大异或

T1，首先考虑我们希望最高位尽可能大，于是必然有一个串为原串 $S$，考虑希望尽可能把高位的 $0$ 变成 $1$，而由于要保证位数足够，于是只能由更高位的 $1$ 为起点的子串来把它变成 $1$，而显然只有最开始的一段 $1$，于是能够高位 $0 \to 1$ 的数量就是 $\min(cntp_0,cntp_1)$，其中 $cntp$ 表示第一段 $0/1$ 的数量，剩下的异或做一下就好了。

P15762 [JAG 2025 Summer Camp #1] Inside Yamanote

T2，不简单的啊兄弟。

首先考虑这个贡献其实只与每个 $x,y$ 被算的次数有关，而具体怎么匹配其实是无关的，于是我们考虑记录 $b_i$ 表示 $i$ 被算的系数，对于一组搬家即 $b_x +1,b_y - 1$。

我们需要最大化 $\sum d_ib_i$，考虑如何构造 $d_i$，你发现限制条件只有 $|d_{i + 1} - d_i| \le L_i,d_i \ge 0$，同时我们要求存在某个首都使得 $d_i = 0$。

不妨设 $0$ 为首都，你发现事实上以哪个点为首都是无所谓的，因为我们可以把所有的 $d$ 加上同一个值，而由于 $\sum b = 0$，因此同时加上一个值也不会影响结果，于是我们只需要令最小的 $d$ 作为起点即可。

考虑这个贡献形式如何算，你发现只考虑 $d$ 的结果还是并不好算，考虑 $d$ 的差分数组 $x_i$，每个 $x$ 将会在后缀所有的 $d$ 中被算一次，即我们设 $c_i = \sum\limits_{j>i} b_j$，则 $x_i$ 会被算 $c_i$ 次，问题转化为每个 $|x_i| \le L_i$，且满足 $\sum x_i = 0$，最大化 $\sum x_ic_i$，考虑贪心计算系数，按照 $c_i$ 排序后我们让一段后缀的系数尽可能大，前缀尽可能小，而带权中位数的位置用来补全两边的贡献差。

于是问题变为单点修，求带权中位数，可以树状数组二分维护做到 $1 \log$，用了二分套树状数组两个 $\log$。

P17170 未来

这就是我们的蓝题。。。太难了啊，我他妈怎么，完全不会做的。

考虑如果第一行不进行任何操作，此时每一行每一列的限制，我们可以用二元组 $(r,x)$ 来描述，表示改行/列上限限制为 $r$，在第一行不进行操作时改行需要进行一次操作 $x$。

考虑此时第一行操作 $v$，每行/列的贡献会变化为 $x \oplus v$，考虑此时这行/列需要操作几次，记 $h$ 表示改行限制 $r$ 的最高位，分讨：

• 若 $v \oplus x > 2^{h+1} - 1$，此时无论进行多少次操作均无法达到这个值，贡献为 $inf$。
• 若 $2^{h+1} - 1 \ge v \oplus x > r$，此时无法一次操作直接搞出来，但可以两次操作，只需要第一次把最高位弄出来，第二次把其余的放进去，贡献为 $2$。
• $r \ge v \oplus x > 0$，此时一次操作即可达到，贡献为 $1$。
• $v \oplus x = 0$ 此时贡献为 $0$。

通过差分，我们可以对于 $[l,r]$ 加入对应的贡献。使用 trie 树能够找到 $x \oplus v\le r$ 的 $v$ 对应子树，对子树打 tag，答案为根走到叶子的 tag 之和最小值。

9.23 专题数数，杂题

今天运动会诶，早上去看了开幕式，和同学呆在一起玩还挺开心的，回机房发现冠军套上了，那还说啥了直接 648 走起！全款拿下，心情大好啊。居然还有人来找我聊天，今天确实是好日子啊！

P15947 [JOI Final 2026] 集邮 5 / Collecting Stamps 5

哎，这题没做出可惜了。

让你对于每个点 $s$ 求有多少个 $t$ 满足 $dep_t \le D$ 且以 $s$ 为根时，$t$ 的祖先中存在 $u$ 满足 $t_u \le dep_u$。

考虑暴力就是直接枚举 $s$ 然后一遍 dfs 找到所有合法的 $u$，其子树内深度不超过 $D$ 的点均可以选，接下来就不会了。

考虑点分治，我们如何统计答案呢，看上去困难，但实际上我们可以分讨 $u$ 位于 $s \to rt$ 还是 $rt \to t$：

• $s\to rt$，要求 $dep_u - dep_x \ge t_x$，考虑点分治显然需要把限制独立到每个点上才能统计，所以移项得到 $dep_u \ge dep_x + t_x$，维护路径 $\min$，若存在满足条件的点则任意经过 $c$ 长度不超过 $D$ 的路径均合法，对于 $t$ 的限制就只有 $dep_t \le D - dep_s$。

• $rt \to t$，要求存在 $x$ 满足 $dep_u + dep_x \ge t_x$，同样移项得 $dep_u \ge t_x - dep_x$，同样维护路径 $\min$，此时限制为二位偏序，分别限制在 $dep$ 维和 $\min (t - dep)$ 维，直接做二维数点即可。

哎，中秋节怎么一直在摆摆摆，不管了。

9.27 ~ 9.28 ？？？

落下的东西有点多，来补一补。

9.24 模拟赛

T1，考虑从 $n$ 到 $1$ 依次确定每个数的位置，首先每个位置有一个填数的上界，也就是包含该位置的所有限制中 $x$ 的最小值，对于当前填的数 $i$，考虑维护满足上界 $\le i$ 且还没有填的位置数量，这些位置之间是彼此不区分的。但是要注意，当存在一些位置满足限制恰好为 $i$，此时 $i$ 只能填在这些限制的位置中，我们维护一个变量 $cnt$，若存在限制恰好为 $i$ 则能够填的是限制为 $i$ 的位置数量 $c_i$，否则能填的为 $cnt$，并在每次填之后 $cnt \leftarrow cnt - 1$ 即可。

9.24 T3

原来核桃省选前集训做过这个题，但是现在看还是只记得它要倍增值域分块，哎其实也没想，反正直接来写一下吧。

我们先考虑一个区间的权值如何快速计算，考虑这样的做法，我们设初始的 $mex = 1$，每次加入一个数 $x$，如果当前 $x > mex$ ，则暂时无事发生，否则这个 $mex$ 将会增加，这里可以参考山河重塑这题，发现当新加入的数 $> mex$ 就没有用，否则会对前缀和起贡献，不难发现 $mex=$ 前缀和 $+1$。

但是这样做还是很慢，怎么办呢？这里有一个非人类的观察（KSCD_ 场切了，所以他非人类），考虑倍增值域分块，接下来我们考虑不断加的这个过程，加入 $mex$ 在第 $i$ 个块内，如果第 $i$ 个块内存在一个 $\le mex$ 的数，那么它就可以产生贡献，并且使得这个 $mex$ 翻倍，就能升到下一个块内。

由此我们可以 $O(\log V)$ 依次 check 这个 $mex$ 能不能升到下一个块，条件就是 $pre_{i,r} - pre_{i,l-1} + 1 \ge \min(B_{i+1})$，其中 $pre_{i,r}$ 表示对于原序列前 $r$ 位置的数，位于倍增值域分块后前 $i$ 个块内的元素的前缀和，$B_{i+1}$ 表示第 $i+1$ 个块内所有元素，也就是如果它前缀和比下一个块的 $\min$ 还要大，他就能吃掉下一个块的最小值并翻倍到更高的块。

接下来我们需要考虑一些性质来把单个区间计算贡献扩展到全局贡献，考虑把区间放到 $l,r$ 平面图上，对于一个区间的 $mex$ 如果能跳到 $i$ 块，那么把区间 $l$ 减小或 $r$ 增大，都只会使得前面条件的左边更大右边更小，也就是说在区间扩大的过程中条件更容易满足，因此对于一个合法区间，它左上角的部分都是满足的。

于是我们能画出一条折线来刻画这件事情，我们又发现对于 $l$ 从小变大的过程中，合法的 $r$ 一定是单调不降的，因为 $\min$ 是在变大的，而前缀和是在变小的，于是我们可以考虑用单调队列维护区间 $\min$，考虑 $mex$ 在第 $i$ 块产生贡献的区间，一定是能够爬到 $i$ 但是爬不到 $i+1$，因此我们可以对于 $\log$ 层逐层维护出这条折线，然后对于每个 $l$ 统计贡献。

具体统计贡献可以对前缀和的系数做差分，是一个区间加单点查，最后前缀和一下贡献即可，就是你考虑一下每个 $s_i$ 被算的系数。

9.26 模拟赛

T1，一个很直觉的想法就是从左到右，最左边填上 $a_1 - 1$，然后剩下的位置根据限制从左到右填最大值。感觉一下，假如某个位置你没有填到最多，那么你把它调整到最多之后，对于后面的减少量不会超过该位置增加量，且后面的限制更加宽松，于是这样是最优的。

T2，这是怎么观察出来的呢。

考虑对于给出的每个 $x,t$，计算从 $x$ 出发，到达终点需要的时间 $h$，记录 $s_i = t + h$，表示到达终点的最快时间，则要实际上我们就是对 $s$ 求一个 LIS，为了处理小数情况可以乘上 LCM。

感觉主要是你要考虑，删除啥样的其实是，挺困难的，因为两两之间都有影响，那么你可以，考虑一下最终留下来的东西要有什么性质，这样子。

然后应该就能考虑到，保留下来的东西的一些限制。

T3，

CF2268

A

考虑如果前后缀是不交的，那么此时一定会一直删一直删，直到两个位置有交，也就是当 $2k \ge n$ 时，我们会先把 $[k,n=k+1]$ 全部选上。考虑接下来的操作，无论左右，都会使得两个位置向外移动一个，于是我们取其中较大的一个选择即可。

B

哦哦的 no，这题好难 /ll。

我们尝试分析一下所有 $3k$ 的二进制有什么性质，你发现这些二进制是 $0011,0110,1001,1100,1111$，这些东西组合一下就能够对任意两位进行操作或操作整个串，同时我们发现无法组合出方案去操作奇数个位置，于是 popcount 为奇数的位置必定不合法。设有 $m$ 个数 popcount 为奇数，我们得到了答案的上界为 $n-m$。

有一个性质是你可以同时操作任意两个数 $(a_i,a_j)$，只需要依次操作 $(a_i,a_{i+1}),(a_{i+1},a_{i+2})\dots (a_{j-1},a_j)$。把 popcount 为偶数的数称为“好数”，我们尝试做到上界。

若 $m \ne 0$，我们把所有好数与某个非好数进行操作，由于非好数一定不合法，我们不需要关心它被操作成了什么，同时一定能通过操作把好数变得合法，于是该情况下可以做到上界。

否则序列中全部为好数，我们先随意取出一个数，假设取出了 $a_1$，对于其它的每个数 $a_i$，我们把 $a_1,a_i$ 同时操作上 $a_i$，进行完所有操作后序列变为 $x,0,0,0,0\dots 0$，其中 $x = a_1 \oplus a_2 \dots \oplus a_n$，不难发现 $x$ 依旧是好数。

同时我们发现所有好数中只有 $5,10$ 不能被 $3$ 整除，于是当 $x = 5/10$ 时，我们把 $a_1,a_2$ 同时操作上 $3$ 即可变为 $0110/1001,0011$，于是我们做到了上界。

因此只需要维护序列中 popcount 为奇数的数的个数即可。

C

考虑我们从高位向低位进行构造，在这个过程中如何 check 一个候选的答案 $X$ 是否合法，首先按位与操作对按位异或操作有分配律，于是我们可以把式子看作是 $a_v \& (a_l \oplus a_{l+1} \oplus \dots \oplus a_r)$，于是首先有要求 $a_v \& X = X$，同时我们只关心 $X$ 中的这些位，也就是在按位与时我们可以使用 $X$ 来代替这个最大值 $a_v$。

于是有两条限制，$a_v \& X = X$ 且 $(a_l \& X) \oplus (a_{l+1} \& X) \oplus \dots \oplus (a_{r} \& X) = X$，发现贡献与序列上区间 $\max$ 有关，考虑建笛卡尔树，我们对于每个 $v$ 作为最大值的点 check 它作为最大值的区间内是否存在合法区间，暴力的做法是扫描左/右端点，找到对应的右/左端点，而对于这类笛卡尔树上扫描端点的东西可以考虑启发式合并，我们只扫描较小的一半，则扫描的次数是 $O(\log n)$ 的，单轮操作 $O(n\log n)$，从高到低决策每一位，一共进行 $O(\log V)$ 轮。

9.29 模拟赛

T1，哎，感觉，真的最不会做的就是，需要一些推式子的题。其实，可能也不难，哎但是还没想好怎么做。

T2，挺好玩的一个题，其实非常简单但是做麻烦了。尝试先把最高位凑出来，也就是我们凑出来每个 $2$ 的幂，你考虑最简单的是你凑出来 $2^k - 1$，你发现你同时需要 $2^k + 1$，于是你能用 $3n$ 次操作凑出来所有的 $2^k$ 和 $2^k -1$，然后从大到小构造 $n$ 的每一位，为了满足所有数 $\le n$，只需要在为 $1$ 的位置操作上 $2^k - 1$ 即可。

10.2 信星社模拟赛

链接

T1，考虑最开始 $a_0$ 的范围为 $[0,H]$，考虑一个贪心策略是你从前往后处理询问，每次根据询问的 $b_i$ 确定出新的该位置的值域 $[L,R]$，当不存在合法区间时我们删掉这一个询问，然后把区间重新改回 $[0,H]$。

考虑贪心的正确性，若该区间起点为 $s$，第一个需要删除的询问为 $b_t$，则我们在 $[s,t]$ 中必然会删掉一次询问，而删除掉最右边的询问显然会取到最大区间。

T2，首先不难注意到交换两个位置 LIS 最大只会产生 $1$ 的改变，于是只需要考虑升序对交换会不会 $-1$，降序对交换会不会多 $1$。

记录 $f_i$ 表示 $i$ 开头的 LIS，$g_i$ 表示 $i$ 结尾的 LIS，则首先交换降序对是好做的，直接把两个 $f$ 和 $g$ 加起来即可，看是否会更大。

考虑我们需要处理出哪些位置是关键的，也就是必须出现在 LIS 中的点，记 $L$ 表示 LIS 长度，按照 $f_i$ 分层扫描，一个位置是关键的当且仅当 $f_i + g_i - 1 = L$ 且该层只有这一个位置。

这是因为你的 $f$ 一定是逐层加上去的，也就是说你每层必须取一个 $f$，于是就得到了合法的条件。

10.3 dmy Div 2

T1，kruskal 重构树板子，直接写就好了。

T2，还没看。

T3，最开始读题读错了，读成了差 $\le k$，发现一个性质是所有逆序对必须交换，于是显然只需要考虑差最大的逆序对，而这个可以直接对 $l$ 扫描线，我们开线段树维护每个 $i$ 作为右边那个数时，该逆序对差值最大值，你发现当不满足逆序对时贡献为负数，于是我们不需要关心是不是真的逆序对，只需要维护 $[l,i)$ 中最大值即可，使用单调栈，加入 $l$ 时对 $[l,r_l]$ 做区间修即可。

考虑和的情况，你发现此时你维护最大值就需要考虑是不是逆序对了，考虑对于 $i$ 维护 $l_i$ 表示最大的满足 $j a_i$ 的 $j$，我们尝试说明最大逆序对只会出现在这之中。

首先若存在其它的 $k$，分讨，若 $k \le a_j$ 则显然选择 $j,i$ 更优，否则选择 $k,j$ 更优，在前面会被算到，不需要考虑。

于是只需要按照 $r$ 扫描线，加入一个数时贡献到 $l_i$ 上，贡献为 $a_i + a_{l_i}$，询问区间最大值。

10.7 ？

对，太摆了，他哥的直接就跳到 10.7 了，但是不管了，好像做了 $0$ 个有意义的题。

P17537 [JAG 2026 Summer Camp #1] Rabbit, Rabbit, Rabbit

首先你发现判断无解是简单的，由于每走一步会改变每个点到它的终点距离的奇偶性，于是要求所有点到终点的奇偶性相同，于是要么奇数 $X$ 配偶数 $Y$，要么奇数 $X$ 配奇数 $Y$，偶数同理。

一个想法是我们知道配对之后，想要像其它题一样最小化一下操作次数，也就是按照升序排序后对应配对。考虑这个为什么是对的，$L \times R$ 这个形式有点难处理，我们拆到任意两个点 $i,j$ 上，他们的贡献是 $i$ 与 $j$ 移动方向不同的次数。

记录 $d_i$ 表示点 $i$ 的位移大小，答案有下界 $\frac{1}{2}\sum_{i < j} |d_i - d_j|$，这个下界是可以做到的，我们令所有点在到达终点后的操作为 $LRLR$，同时令每个点先走完需要向右走的步数，即可求出任意两个之间的差值，构造得到答案下界。

T824347 调配课时

二分答案，对于 $a_i \ge b_i$ 的部分优先用 $a_i$ 填，不够的从其它的地方找 $b$ 用，多余的扔给其它地方 $b$，对于 $a_i < b_i$ 的部分直接全都用 $b$ 就行了，只需要判断 $b$ 够不够用。

T824348 接驳专线

首先有一个比较好想到的就是，你直接按照 $dis_{s,u} + c_u$ 从小到大扫，双指针维护合法的 $v$，但你发现这样可能会存在 $u$ 能扫到 $v$，$v$ 也能扫到 $u$ 的情况。此时去重你需要三维偏序，那要咋搞。

一个发现是不存在这样的情况。考虑首先特判掉 $dis_{s,t} \le K$ 的情况，于是我们需要说明存在合法的 $u,v$，一定不同时满足：

• $K \ge L + dis_{s,u} + a_u + a_v + dis_{v,t}$
• $K \ge L + dis_{s,v} + a_v + a_u + dis_{u,t}$

将上下两式相加，得到 $2K \ge 2L + 2(dis_{s,u} + dis_{u,t}) + 2(dis_{s,v} + dis_{v,t}) + 2(a_u + a_v) \ge 2dis_{s,t}$，而与我们前面说的 $dis_{s,t} > K$ 显然相违背，于是不存在这种重复的情况。

于是第一种做法就是你直接双指针，然后去掉有连边的情况就行。

以及 lldxjw 思考了 $0$s 就会了的做法，直接维护一个已经算过了的 $dis_{s,u} + a_u$ 的集合，当我们要加入一个 $v$ 时就计算 $v$ 能与多少集合内的 $u$ 产生贡献。由于从小到大加入，我们可以做到不重不漏。

T824349 维修网络

一眼丁真这不是让我们赢得选举吗，所以就不用写做法了就这样吧。

10.8 模拟赛

哎说实话真的一个题也不会啊，做到后面就不想做了，不管了做别的题去了。

P1484 种树

若不存在 $k$ 的限制，显然可以设 $f_{i,0/1}$ 表示考虑了前 $i$ 个，$i$ 的位置选/不选的最大贡献。考虑最优决策关于限制的 $k$ 是上凸的，于是可以套一层 wqs 二分解决。

AT_abc464_g [ABC464G] Celester 2

考虑记录 $a_i$ 表示把 $s_i,s_{i+1}$ 变为 RS 需要的操作次数，有 $a_i \in [0,2]$，考虑求出 $f_i$ 表示选出 $i$ 个互不相邻的 $a_i$ 的最小和，则答案为最大的 $i$ 满足 $f_i \le k$，$f_i$ 的求法参考种树。

wqs 二分

感觉又是，第二遍或者第三遍学了，反正感觉之前学的可能也不是很明白，那就再学一遍嘛。

首先 wqs 二分解决的是啥问题，先看两个例题吧：

• 给定 $n$ 个物品，每个物品有价值，求选恰好 $k$ 个的最大价值。
• 一棵树树边有黑白两种颜色，求恰好 $k$ 条白边的生成树边权和最小值。

你发现这类问题具有一些共性，若不考虑题目限制的 $k$ 问题是非常好做的，并且我们可以用 $O(n)$ 左右的复杂度求出答案以及达到该答案需要选择多少个物品。

比如对于 MST 若不限制恰好 $k$ 条白边，我们可以快速求出 MST 权值以及选择了多少条白边。

记录 $f(x)$ 表示限制 $k = x$ 时对应的答案，则问题均满足 $f(x)$ 关于 $x$ 具有凸性，即 $f(x) - f(x - 1) \ge f(x+1) - f(x)$。比如在第一个问题中，我们显然会选产生增量最大的物品，若存在操作选择的不是增量最大的物品，我们把增量最大的物品在这次操作选择显然更优。

当 $f(x)$ 关于 $x$ 上凸，且我们能够快速求出不限制 $x$ 时问题的答案以及操作次数，就可以使用 wqs 二分解决这类问题。

以第一个问题为例，解释一些 wqs 二分在干啥。

我们现在希望能求出某个特定的 $k$ 对应的 $f(k)$，但我们只知道 $f(k)$ 具有凸性，如何求出这个问题。

把所有 $(x,f(x))$ 放到二维坐标系上，相邻点连线能够连出一个上凸包。枚举一个斜率为 $c$ 的直线 $y = cx + b$ 去切这个凸包，由于凸包的性质我们切到的点满足截距最大，此时 $b = f(k) - c \times k$。

考虑右边的式子的意义，相当于在原有的每个物品价值的基础上，选择一个物品会消耗 $c$ 的价值，而我们求出的这个 $b$，相当于在不限制选择物品数量的前提下，选择一个物品需要消耗 $c$ 的价值，求能选出的最大价值。该问题显然可以在 $O(n\log n)$ 的时间内解决，同时我们可以求出选择了多少个物品。

也就是我们求出了该问题下选择的物品数量 $k$ 以及对应的 $f(x) - c \times k$，当 $c$ 逐渐变大时，我们趋向于选择更少数量的物品从而减少消耗的代价，从而最优的 $k$ 关于 $c$ 同样具有单调性，由此我们可以二分斜率 $c$，必然会在某个位置取到 $k =$ 我们询问的 $K$，此时可以根据答案反解出真实的 $f(k)$，从而求出答案。

以及在 wqs 二分过程中可能有一些容易误解的地方，首先是注意你在求解无限制的问题中，求出的是 $cnt$ 最小还是最大的答案，若为 $cnt$ 最小的答案，则二分要写成 if(x <= m) r = mid - 1,res = mid;else l = mid + 1。

同时要注意你最终二分出的斜率 $c$ 一定是能够切到 $m$ 这个点的，但可能存在多个点共线的情况，此时你根据 $b$ 反解 $f(m)$ 时，由于我们要解的是 $f(m)$，于是答案为 $ans - m \times mid$ 而不是 $ans - m \times cnt$。

T1，就是他哥的，不知道难点在哪啊。

维护每个块，为了最优化操作次数我们能合并就合并，能合并的条件是位置相邻且值域相邻，维护一个栈，判断相邻两个块需要正着还是倒着合并，维护正着和倒着的代价即可。

T2，考虑取出某个位置为根，你发现根选择的这条弦可以把两边划分为互不干扰两部分，而每个部分只会向外连一条边，也就是任意合法结构都可以被划分为三部分，其中端点两部分有连边。一个朴素的 dp 是设 $f_{l,r,k}$ 表示区间 $[l,r]$ 完成配对，向外连边的点编号为 $k$ 的方案数，转移考虑划分为三部分，中间的区间向外连边，两边的两个区间之间连边，要求区间内 $|cnt_r - cnt_b| = 1$ 且两个区间分别为 $1,-1$，并且要求两区间颜色能够匹配。

你发现记录 $k$ 这一维是没必要的，因为你可以通过区间确定出连出去的是什么颜色，从而只需要记录 $dp_{l,r}$，朴素 dp 的复杂度为 $O(n^4)$。

考虑一步一步转移，先合并左半部分和中间部分，维护一个辅助数组 $g$，然后用 $g$ 转移右半部分，时间复杂度 $O(n^3)$。

T4，首先原序列可以划分为若干个连续段，每个连续段中保留一个数。我们尝试刻画保留的序列合法的条件，首先对于每个区间 $[l,r]$ 若保留下来的位置为 $t$，需要满足 $a_l \ge a_t \ge a_r$，可以归纳说明这样一定能够消除掉整个区间，首先一定存在相邻的逆序对，不断选择不是边界的那个数删除即可。

同时由于要求最终保留的序列不能再操作，于是最终序列 $b$ 需要满足 $b_1 < b_2 < b_3\dots < b_m$，且任意两个相邻位置之间存在 $t$ 满足 $b_i \ge a_t,a_t < a_{t+1},a_{t+1} \ge b_{i+1}$。

同时第一个保留的位置 $x$ 需要满足 $a_1 \ge a_x$，最后一个位置 $y$ 满足 $a_y \ge a_n$。

于是可以得到一个朴素 dp，设 $f_i$ 表示考虑了前 $i$ 且 $i$ 必须保留的方案数，转移枚举上一个保留的位置 $j$ 判断是否合法即可，实现一下可以做到 $O(n^2)$，其中位置 $t$ 的限制可以搞成，维护 $\le a_i$ 的 $t$ 的 $a_{t+1}$ 的最大值，然后就可以快速判断是否合法转移。

优化好像是 cdq 分治，限制可以写成一个二维数点的形式，但还不会所以先不写了。

叶落有时

自己出的题，大概就是一棵 $1$ 为根的树，每个点有黑白色，一次操作是把一棵子树挂到叶子上，最小化操作次数使得所有叶子深度都相等。

首先对每个点维护 $d_i = dep_i - c_i$，表示每个点的修正深度，于是目标变为让所有叶子的修正深度均为 $D$。

考虑一个暴力，从大到小枚举最终所有叶子的修正深度 $D$，可以在 $O(n)$ 的时间内判断一个 $D$ 是否合法，由于更大的 $D$ 所需要的操作次数一定不大于小的 $D$ 的操作次数，于是找到最大的合法的 $D$ 输出答案即可。

暴力判断 $D$ 是否合法只需要贪心的从叶子向根合并，若当前叶子修正深度已经达到 $D$ 则需要断开边，若当前依旧连通的子树内存在两个叶子修正深度相同则该 $D$ 不合法，否则看最终所有叶子是否修正深度相同即可。

但实际上我们可以把每次 check 的时间复杂度做到更优，考虑每次找到还未被处理的，修正深度最大的叶子 $x$，设 $d_x = M$，则它最终所在的块根节点 $u$ 满足 $dep_u = M - D + 1$，也就是需要找到 $x$ 的 $D+c_x-1$ 级祖先 $u$，对 $u$ 进行操作。

若 $u$ 当前子树内的所有叶子最大修正深度 $< M$ 则该 $D$ 不合法，因为若在深度更小的位置操作则 $x$ 不合法，否则其它的叶子不合法，于是合法条件为 $u$ 当前子树内所有叶子修正深度最小值为 $M$。

同时由于所有点的深度只会减少不会增加，于是在任意时刻若存在某个叶子修正深度 $< D$ 也可以判断 $D$ 不合法。

此时我们需要支持进行询问子树最小值、全局最大值，单调赋值、子树清空，按照原树的 dfs 序，线段树维护这些信息即可。由于每次操作至少会把 $D$ 个点挂到根上，也就是原树会减少 $D$ 个点，于是单次 check 的时间复杂度为 $O(\frac{n}{D} \log n)$，而 $\sum\limits_D \frac{n}{D}$ 为调和级数，于是总时间复杂度 $O(n\log^2 n)$，空间复杂度 $O(n)$。

要注意每次线段树只能清空用到的部分，否则复杂度会退化成 $O(n^2)$。

10.9 专题，凸优化？

P17543 [JAG 2026 Summer Camp #2] Deque Bracket Optimization

哎这题挺好的，很厉害，实际上也是括号序列另一种生成方式？

考虑左端点位置是必选的，接下来对于任意的 $i$，$w_2,w_3,\dots,w_{2i+1}$ 中必然要选出 $i$ 个作为左括号，于是我们可以维护一个堆，每次取出最左边两个位置加入堆中，然后取出堆中最大值作为左括号。

同时也可以对右端点这样做，维护一个小根堆每次取出其中最小的选作右括号。并且该两种选法选出的点应当是互补的。

于是我们可以同时维护，分别维护大根堆 $N$ 维护当前还没被选作左括号的点，以及小根堆 $Y$ 表示已经选作左括号的点。维护 $F,L$ 分别表示开头和结尾元素。由于我们同时维护了两种贪心，从而可以保证无论是从左端插入两个数还是从右端插入两个数，都可以在其中一端作为最后一个决策，从而能够保证贪心的正确性。

若在开头加入 $a,b$，则将 $b,F$ 加入到 $Y$ 中，弹出 $Y$ 中最小值加入到 $N$ 中。若在结尾加入 $a,b$，则将 $L,a$ 加入到 $N$ 中，取出 $N$ 中最大值加入 $Y$，计算对应的贡献。这样我们对于任意端点插入，都在一端进行了正确的贪心，并且由于两个堆互补，我们可以对应的修改另一个堆，保证了正确性。

考虑两端各插入一个数怎么做，我们维护两个上述结构 $all$ 和 $ins$，其中 $all$ 维护整个序列的该结构，而 $ins$ 只维护去掉两个端点后的序列结构，此时若进行两端插入操作，实际上新的 $ins$ 会变为原来的 $all$，而新的 $all$ 相当于在原本的 $ins$ 进行了两次端点加入操作。

哎，反正是，很牛的一个题啊！。

AT_arc168_e [ARC168E] Subsegments with Large Sums

额啊？

首先你发现题目要求的这个东西是不具有凸性的，但显然具有单调性，考虑二分答案 $x$，如何 check 一个 $x$ 是否合法？

记录 $g_x$ 表示允许段与段之间不连续，选出 $x$ 个 $\ge S$ 的段，至少需要多少长度，你发现要求 $n - g_x \ge k - x$，移项得到 $n - k \ge g_x - x$，于是我们把贡献从 $r - l + 1$ 改为 $r - l$，恰好使得 $g_x$ 的贡献减少了 $x$，于是要求变为 $n - k \ge g_x$。

显然 $g_x$ 具有单调性，同时感性理解，我们肯定先选择短的段，再选择长的段去贡献，于是 $g_x$ 应该具有凸性，于是我们可以直接套一层 wqs 二分求解 $g_x$，内部问题变为我们要从序列中选出若干个连续段，每选出一段能得到 $mid$ 的收益和 $r - l$ 的代价，求最小代价。这样就得到了 $O(n \log^2 n)$ 的做法。

考虑每次二分一个 $x$ 就要 wqs 二分 $O(\log n)$ 轮，你发现过程中会产生非常多冗余的计算，考虑我们实际上是要在凸包上找 $f(x) \le n - k$ 的最大的 $x$，于是直接二分斜率，判断是否可行即可，这样可以少一个 $\log$。

哎感觉写后面的题之前，先简单写一下决策单调性吧。

如果一个 dp 具有决策单调性，其实不只是 dp，只要一个东西的贡献具有决策单调性，也就是对于 $i,j$ 设贡献分别为 $f(i),f(j)$，使得其取到最大值的位置分别为 $x,y$，如果对于 $i < j$ 有 $x \le y$ 那就可以分治来解决，分治维护当前需要处理的区间以及该区间内决策点的区间，也就是 sol(l,r,ql,qr) 表示处理 $[ql,qr]$ 的询问，决策点位于 $[l,r]$ 内，可以做到 $1\log$。

QOJ #5507. Investors

首先考虑转化一下题意，分析一些显然的性质。

每次操作右端点一定为 $n$，因为这样对于后面的影响是不劣的，于是每次操作的是一段后缀。

显然每次可以加一个极大的数，每次操作的左端点把整个序列划分为了 $k+1$ 个段，段与段之间不会产生贡献，于是问题转化为把整个序列划分为 $k+1$ 个段，最小化每个段内逆序对数量的和。

考虑一个暴力 dp 是你设 $f_{i,j}$ 表示前 $j$ 个分成 $i$ 段的最小逆序对数量，维护 $w_{i,j}$ 表示区间 $[i,j]$ 内的逆序对数量，考虑暴力转移需要枚举 $k$，从 $f_{i - 1,k} + w_{k+1,j}$ 转移。

考虑这个东西实际上是有决策单调性的，你考虑相交和包含的情况，发现不交的部分在包含中会多算一次贡献，于是相交优于包含，可以得到决策单调性，从而直接上分治，按 $i$ 分层做，每层分治转移即可，时间复杂度 $O(n^2 \log n)$。

10.10 模拟赛

哎，都 10.10 了，还是很，菜，状态还是很不好，甚至感觉最近，老是被简单题创飞，而且代码能力也还挺拉的，说实话还是很慌的吧。

T1，考虑要算不经过这个矩形的路径数量，你发现在矩形的左下和右上角画两条竖线，则所有合法路径一定都从左向右经过这两条竖线，于是组合数算一下贡献就好了。

T2，哎其实是很好的一个题啊，首先你发现可以删掉路径上某条边，最后保留边权最小的一条边，然后就做完了？

你发现大样例不对啊，怎么还能接着删的，然后你玩一玩 $s,t$ 之间有连边的情况，发现确实可以通过 $2$ 次操作吧边权转化为 $s$ 或 $t$ 连着的一条边，进而继续推一下你发现可以通过 $dis + 2 + w - 1$ 次操作把 $s,t$ 的距离变为一条边的边权，其中 $w$ 表示 $s,t$ 路径上的边数，$dis$ 表示这条边的端点到 $s\to t$ 这条链的最短边数。

然后就做完了。

T3，好像是类似转移对值域有限制，把值域拆成高低位，然后分别找？还没看懂啊。。。

dp

10.11

AtCoder Regular Contest++ 232

怎么说呢，反正会不会做的，既然做了就补一下吧，反正今天放假。

AT_arc232_b [ARC232B] Two Flips

考虑操作会长成什么形式：

• 操作 $a_1$ 和某个 $j$，记录 $j$ 的反面为 $x$。
• 操作 $j$ 和某个 $k$ 满足 $a_k = x$，记录 $k$ 的反面为 $y$。
• 操作 $k$ 和某个 $k^{\prime}$，满足 $a_{k^{\prime}} = y$。
• $\dots$
• 操作 $i$ 和 $a_2$。

若存在某次操作不在这条链上，若它位于最终最有答案上，我们一定可以调整操作顺序使它位于这条链上，否则该操作是多余的，没必要进行。

考虑建图，对每个 $i$ 连边 $a_i \to b_i$，我们先不考虑对于正反面的限制，尝试找到一条从 $a_1 \to b_1$ 出发，以 $a_2 \to b_2$ 结束的路径，可以通过 BFS 解决，唯一的限制是不允许走一条边之后立刻从这条边走回去。

找到一条最短路，就可以最小化操作次数。考虑 BFS 做这件事情，接下来我们尝试说明一定能构造出对应的合法操作序列。

考虑任意一个局面，记录 $x_i$ 表示第 $i$ 张卡牌当前朝上的面在后面被操作的次数，$y_i$ 表示第 $i$ 张卡牌当前朝下的面操作次数，则对于当前朝上面与最终局面相同的卡牌，有 $x_i = y_i$，否则有 $x_i = y_i + 1$，设还有 $W$ 轮操作，则满足 $\sum x_i + y_i = 2W$。

由于当前局面与最终局面不同，于是必然存在 $i$ 满足 $x_i = y_i + 1$，于是 $\sum x_i > \sum y_i$，于是有 $\sum x_i > W$。而若该局面不存在能够操作的卡牌对，则每对卡牌中只能有一个朝上一面为 $v$，每轮操作最多只能产生 $1$ 的 $x$ 贡献，所有牌中当前朝上的一面的使用总次数至多为 $W$，与 $\sum x > W$ 违背。

AT_arc232_c [ARC232C] All Add or Single Negate

考虑如果枚举 $s$ 表示全局加的次数，那么接下来的问题可以看作二分图最小权匹配，我们计算一下 $a,b$ 匹配的贡献。

• 若 $a+s \not\equiv b \pmod{2}$，则两者无法完成匹配。
• 若 $||a| - |b|| > s$ 则无法进行匹配。
• 否则若 $a$ 与 $b,-b$ 中任意一个距离 $\le s$，则可以通过一次反转操作完成匹配。
• 否则只能通过两次反转操作完成匹配。

考虑 $s$ 的枚举范围，找到最小的 $s$ 使得存在完美匹配，由于二分图边权最大为 $2$，于是只需要枚举 $s \in [s_{\min},s_{\min} + 2n]$ 即可，复杂度 $O(n^4)$。

CF2271E Array Emptying

很好的一个题。

考虑拆的数次数越多，就更容易消除掉，于是考虑二分拆分的次数 $c$，总的操作次数为 $2c + n$。首先显然一个数如果确定要被拆分，则在最前面拆分是最优的，考虑我们从前往后做并不好决策哪些数要拆，且拆开的数会加到前面，从而前面决策也会受到影响。

考虑从后往前做，初始记录 $S = 2c + n$，扫描过程中动态维护 $S$ 表示当前的 $k$ 值，我们的策略是，能删一个数则立刻删掉，否则拆掉它。

首先从大到小删是最优的，若某次能删一个最大值而我们删除了一个较小值，那么交换这两次删除操作一定不劣。同时能删除一定不进行分裂操作，我们可以把分裂操作留给后面，这样一定不劣。

CF2271F Beautiful Pillers

首先有一个观察是我们可以通过把 $a_1,a_n$ 修改为 $10^9$ 使得整个序列合法。于是答案最多为 $2$，考虑如何判断答案是否为 $1$，考察全局最大值的位置，你发现 $a_1$ 和 $a_n$ 几乎是最难满足的限制，设全局最大值为 $mx$，位置为 $p$，排除掉 $ans = 0$ 的情况，考虑不合法的位置，我们通过把 $a_1$ 操作成 $mx$ 或把 $a_n$ 操作成 $mx$，可以消除掉从 $p$ 向左或向右一半的非法位置，不难发现操作任何其它位置都无法同时消除左右两半的不合法位置。

于是考虑尝试把 $a_1,a_n$ 分别修改为 $mx$ 判断是否能够合法，剩下的不能通过该方案调整的就只有 $p$ 两端均存在不合法段。我们声称只需要把 $p$ 调整为 $1$，就可以把所有能够成功调整的情况覆盖到，接下来来说明这件事。

首先若 $p$ 调整成更大显然不会更优，而若希望把 $a_p$ 调整成一个 $x$，与其它数配对，首先若只有左右中的一边能与 $p$ 配对，由于我们这种情况下 $p$ 左右均存在不合法的段，于是这种方案无法调整成功。否则 $p$ 与左右均构成合法对，此时把 $p$ 调整到更小，其左右两个配对的端点可以构成一个新的合法对，形如 $X(a_l)\dots X(a_p) \dots X(a_r)$，此时把 $a_p$ 调整成 $1$ 后 $l,r$ 同样可以配对，于是可以覆盖到所有情况。

对于有多个 $mx$ 的情况，显然 $mx$ 之间不存在不合法区间，而若找到最左端的和最右边的 $mx$，记作 $L,R$，若在 $L$ 左边和 $R$ 右边均存在不合法区间，则显然无法通过一次操作让两个区间合并或同时合法。

于是只需要尝试把 $a_1,a_n$ 调整为 $mx$ 以及把任意一个最大值的位置 $p$ 调整为 $1$，判断是否合法即可，判断合法可以单调栈做到 $O(n)$。

P7065 [NWRRC 2014] Fragmentation

唉这题也不会，真唐完了。

首先考虑离散化之后，值域不连续的肯定是不能划分在一段的，那么如果你要把 $i-1,i,i+1$ 划分在同一段，是要求 $i$ 只连续出现在这一段内的，于是 $i,i+1$ 连接在一起的次数就只有一次，我们希望最大化这个次数。

于是你可以记录 $f_{i,j}$ 表示考虑了离散化后的值域 $[1,i]$，其中 $i$ 与 $i-1$ 连的编号是 $j$，如果不能连则编号为 $0$，考虑如何转移。

若不能连显然直接 $f_{i,0} \leftarrow \max f_{i-1,j}$。

能连则有 $f_{i,j} \leftarrow \max f_{i-1,k} + 1$。

如果要从 $k=j$ 转移，则还需要考虑合法的条件，于是直接维护前后缀最大值，并特判转移到同一个 $j$ 的转移即可，大概就是你前后各扫一遍分别转移一次就好了。

感觉今天，唉其实做了很少的题，应该至少说都是简单题，就一个延迟钦定 dp 难一些，而且也不是自己做的。怎么说呢，不知道怎么评价，就是，越来越没底，越来越感觉没希望了吧。

10.12

写了两个 dp。

充了个 plus，感觉很牛啊。

反正就是太菜了呗，那其实，就可能就是并没有，找到很好的训练方法，而且可能你也确实，没有很认真训练，没有把所有时间用在训练上。所以就是，就是这样的吧，可能你就是训的时间还是不够多，虽然就是，其实也没有摆。

CF2057E2 Another Exercise on Graphs (hard version)

哎为什么老是不会做这种，比较简单比较可做的题啊。真就是，很搞心态吧。。。

首先考虑对每个询问可以二分答案 $x$，把 $\ge x$ 的边设成 $0$，$

考虑能不能预处理这个东西，从大到小加入每条边，维护最短路，看上去是 $O(n^2m)$ 的，但实际上当两个点之间距离变成 $0$ 之后就不需要再更新了，于是实际上需要更新的只有 $O(n)$ 条边，维护最短路询问二分答案即可，实际上是类似一个最大生成树的树边。

P4768 [NOI2018] 归程

感觉是不是，训练真的出现了很大的问题，导致我已经，不思考了。。。。。。。。。。。。。。。。。。不是为啥啊。。。。。。。。。。。。。。

考虑一次询问实际上是我们可以从 $v$ 出发，走不小于询问的 $p$ 的边走到一些点 $u$，然后从 $u$ 开始只能走路，也就是求一个 $dis_u$。

考虑建出 kruskal 重构树，找到 $v$ 深度最小的祖先 $f$ 使得 $f$ 的点权 $\le p$，此时 $f$ 子树内所有点同样满足点权 $\le p$，也就相当于子树内边均可以走，我们能够走到的点也就是其子树内的所有点。

于是只需要求子树内 $dis$ 的最小值即可，找 $p$ 可以使用树上倍增。

唉，真的讨厌你。

就，可能我确实从始至终都没有厉害过，就是好像除了打的烂完了的 NOIP 和 CSP，也没有什么能说明我的实力，而好像我的实力和去年也没有什么变化，好像我也，只是一直在耗着，好像我也从来都没有什么变化。

但，感觉，虽然可能确实是，题很简单，也没有厉害的人吧，感觉，夏令营，状态还不错吗，打的还行吗，好像，也不知道，也并不是。

10.13 模拟赛

哎确实是一个题都不会，就，可能是状态不好，感觉也可能确实就是我本来就没有能力做出来这样的题。

T1，其实和当时三轮省集那个三色草原很像的一个题，同样是三种颜色，我们可以像那题一样考虑把每个颜色表示为 $0,1,2$，每次操作 $f(i,j)$ 的结果为 $-i-j$，假设从左到右操作的三个数分别为 $a,b,c$，则一次操作相当于把 $b$ 变为 $a+c-b$。

到这里就不会做了，实际上是可以考虑他们的差分的，你发现一次操作会使得差分数组由原来的 $b - a,c - b$ 变为 $c - b,b - a$，也就是交换差分数组两个数。

于是一个序列合法当且仅当初始的差分数组集合与最终差分数组集合相同，且要求第一个位置相同，考虑给各个数按照终止位置编号，则最小操作次数即为逆序对数量。

T2，哎感觉确实是一个非常难的题，GPT 做了 7min，烧了我 5h 20% 的额度。

P4331 [BalticOI 2004] Sequence (Day1)

应该是这类问题的板子题，给定一个序列 $A$，要求构造一个序列 $B$ 使得 $\sum\limits_i |A_i - B_i|$ 最小，且序列 $B$ 单调增。

考虑先去掉序列 $B$ 单调增的限制，把 $A,B$ 分别减去 $i$，此时距离不变，而我们只要求 $B$ 单调不降。此时就有若干种做法，说一下其中的两个做法吧。

第一种是你先考虑假如 $A$ 序列单调增或者单调减要咋做，单调增直接取 $B_i = A_i$ 即可，单调减取中位数。一个想法是把 $A$ 序列划分为若干个增的段，每段取中位数，但这样不一定能满足中位数单调不降，于是我们需要把不满足中位数单调不降的部分中位数合并。从而我们需要用到可并堆进行快速合并。

具体实现就是维护一个队列，当新加入一个数先单独开一段，若该数比最后一个段中位数小，则需要进行合并，同时继续合并剩下的段。

第二种做法感觉其实就是 slope trick，考虑一个暴力 dp 是设 $f_{i,j}$ 表示前 $i$ 个位置，第 $i$ 个填 $j$ 的最小代价，不难写出转移，我们把 dp 记录状态改为 $i$ 个 $\le j$，此时我们枚举 $i$ 填的 $x$，有转移 $f_{i,j} = \min\limits_{x \le j} \{f_{i-1,x} + |a_i - x|\}$，考虑对每个 $i$ 维护点 $(x,f_{i,x})$ 构成的二维平面，每次的贡献为先给每个位置贡献 $|a_i - x|$，你发现当 $x > a_i$ 时选择贡献 $a_i$ 一定是不劣的，也就是每个点的贡献实际上是 $\max(0,a_i - x)$。

于是我们类似 slope trick 维护斜率折点，实际上这个地方还并没有完全看明白，但感觉 slope trick 确实暂时没必要研究，然后这个东西其实知道结论怎么做就好了。

大概就是从前往后扫每个 $A_i$，维护一个大根堆，每次插入两个 $A_i$，弹出堆顶元素，记录弹出后的堆顶，记录这个值为 $b_i$，从后往前扫的同时要把 $b_i$ 对后缀取 $\min$。哎感觉还没看懂，但是看懂了是不是也懒得写了，反正先记下来吧。

::::success[放个代码]

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    priority_queue<ll> heap;
    vector<ll> b(n + 1);

    ll ans = 0;

    for (int i = 1; i <= n; ++i) {
        ll t;
        cin >> t;

        ll a = t - i;

        heap.push(a);
        heap.push(a);

        ll m = heap.top();
        heap.pop();

        ans += m - a;
        b[i] = heap.top();
    }

    // 此前 b[i] 存储 p_i，现在还原最优的不下降序列。
    for (int i = n - 1; i >= 1; --i) {
        b[i] = min(b[i], b[i + 1]);
    }

    cout << ans << '\n';

    for (int i = 1; i <= n; ++i) {
        cout << b[i] + i << '\n';
    }

    return 0;
}

::::

反正这个 T2 就差不多转化一下就是这个题，哎，只能说还是，太菜了。

塔一机宝 A20 通关了，哦哦的耶！

10.14 好像是图论专题？

哎，写这些东西，何尝不是一种，日记呢。

#1117. 【UER #14】蛋糕

考虑每个点能够凑出来的数实际上是一段前缀，记录 $f_i$ 表示点 $i$ 能凑出来的值域为 $[0,f_i]$，则叶子节点的 $f_i = n$，考虑如何从叶子向上递推，讨论 $a_u$ 的两种情况：

• $a_u = 1$，直接对所有儿子的 $f$ 取 $\min$ 即可。
• $a_u = 0$，考虑 $f \le x$ 的儿子数量 $\ge x + 1$ 则可以使得 $\text{mex}= x + 1$，直接从前往后贪心即可。注意到 $\text{mex}$ 最大是点的度数，于是枚举量最大为 $\sum deg$。

CF2081D MST in Modulo Graph

首先这题一看就是要优化建图，你考虑 $x \bmod y$ 这个东西，可以拆成 $x - ky$，我们首先把所有相等的元素合并，然后在序列插入 $kx$，此时连边只需要每个点找前驱即可，点数是调和级数的，做一遍 kruskal 复杂度是两个 $\log$。

CF2057E2 Another Exercise on Graphs (hard version)

前天刚做了，不说了。

P12104 [NERC2024] Managing Cluster

首先考虑答案的上界，为啥兄弟你又没有考虑答案的上界是啥，然后就不会做了（。

考虑答案上界，一个显然的上界是整棵树的最大匹配数，这个可以自下向上简单求出。考虑能不能做大这个上界，也就是恰好构成匹配数对合法方案。

考虑找出目标匹配中的所有边，描述出这些边连接的原配对，比如一条匹配边连接了 $3,5$，我们就加入一组 $(3,5)$ 的匹配，由于匹配不一定能够覆盖所有的点，我们把剩余未被覆盖的点任意配对，这样构成了 $n$ 对。

我们希望对每个位置进行最多一次交换操作，使得最终所有配对的两个元素相同，首先排除掉已经配对好的点对，我们把原本存在配对关系的颜色连边，则最终会连接出若干个偶环。

只需要每次从环中删除掉一个点，接下来依次处理新产生的这条边中被交换过的颜色，最终剩下的会是一个二元环，直接交换即可。

从而证明了答案可以做到上界，且给出了一种构造方案。

AT_arc191_d [ARC191D] Moving Pieces on Graph

咦，分讨题。

设 $dis(s,t) = l$，若存在不止一条最短路，答案为 $2$。否则只有一条最短路，可能是走一条最短路一条次短路。同时考虑若最短路上存在非二度点，则可以走到这个点的邻居使得 $S,T$ 错开，长度 $2l + 2$。

搬的图，咋还有这种情况，这么变态，那只能是 $2d^{\prime} + 2d+ 4$。

P17141 [NOI 2026] 传送

哎，感觉，留了很久，之前可能，也没看懂怎么做的，以及可能就是，有一些好的或者不好的回忆，感受。唉总之，说多说少，唉，不懂。

首先考虑一个点会怎样走，一定不存在先走若干步然后再随机跳的情况，因为这样不如直接从一开始就随机跳。以 $y$ 作为根，每次深度的一段前缀（包含 $y$ 的一个连通块）会直接走过去，其余的随机跳。我们把 $S$ 外的点称为随机点。

找到一个阈值 $k$，记录 $S$ 表示 $dis(x,y) \le k$ 的 $x$ 构成的集合，考虑 $S$ 集合内的数直接走过去，$S$ 集合外的数随机，一直到 $S$ 集合内。

记录 $sum = \sum\limits_{u\in s} dep_u$，记录 $cnt = |S|$，设 $E$ 表示一个随机点需要的期望步数，则满足

$$E = \frac{1}{n} \left( sum + (n- cnt) E \right) + 1$$

解得 $E = \frac{n + sum}{cnt}$，考虑 $E$ 是关于 $k$ 下凸的，推推式子可以发现加入 $c$ 个 $dep = k+1$ 相当于是把前后两部分做加权平均数，考虑二分最低点，check 的方式就是看下一个位置增/减/不变。

如何快速 check 贡献，你发现贡献的计算需要快速求出距离 $y \le k$ 的点的数量及深度和，可以使用点分树维护，于是我们得到了一个 $O(q \log^2 n)$ 的做法。

考虑去掉二分的 $\log$，你发现对于有连边的两个点 $u,v$，满足关系 $|E_u - E_v| \le 1$，感性理解若 $> 1$ 可以通过先走到另一个位置然后再走到 $u$，于是我们不需要每个点都二分，只需要从根向儿子扩展，设父亲 $f = h$，则儿子只需要考虑 $h-1,h,h+1$ 即可。

时间复杂度降到 $O(n \log n)$。

没啥好说的，就是实力本来，就不够，去年没报 APIO 可能只是说，该当本来也不应该是你能够打，本来或许，不管因为啥你确实，就是没做出来，那有啥好说的呢，你确实就是，技不如人，确实就只是，靠着别人都失误了，让自己的排名看上去好看一点，有啥用呢，有啥意义呢。

唉，隔壁同学进 MO 省队了，就是，人家也没停课，我觉得我一直都承认他很厉害，就，可能校领导以及，家长，身边的人都觉得这只是因为他足够努力而我不够，就，唉肯定有很多压力吧，然后，肯定回去，也会被说或者怎么样，就，无所谓吧，心态放平认真训练就好了。

说实话今天，其实是很久以来感觉训练的比较顺利，但好像晚上发生了许许多多事情，从发现同学进省队到，打了个 CF 最后，被封了，就是很不甘心而且，很，唉反正可能心里，并不平静吧。

CF 感觉都不难，没啥好题，不写记录了，明天看看 G 可以写个题解。

10.15 模拟赛

哎，他妈的好菜啊。

T1，看到这个操作想到了二轮省集那个题，这个题有更强的一些性质。设最终进行 $p$ 次操作，一个非常强的限制是 $b-a+p$ 必须是 $n$ 的倍数，于是我们要求所有 $b-a$ 同余，记录 $p$ 表示 $n - (b_i - a_i) \bmod n$。

考虑省集那个题的做法，操作次数为 $kn + p$，我们可以二分 $k$，因为在合法操作序列基础上把每个数操作一次显然是合法的。考虑 check 也只需要判断需要的操作次数是否 $\le mid$。

但该题过程中始终不能出现 $0$，于是我们还需要对于每个 $i$ 要求 $cnt_i \le i+1$，其中 $cnt_i$ 表示 $a_k \le i$ 的数量。要注意这里需要 check 到 $\min(n,T - 1)$ 而不是 $\min(n,p-1)$，$T$ 表示操作次数。

T2，还不会。

T3，感觉很厉害的一个题啊。

首先考虑一个区间合法的方案，对于这类题，我们能够给出一个充要条件：不存在 $i a_j > a_k$。考虑若存在则显然三个两两之间不能染相同颜色，否则以每个点结尾的下降子序列长度不超过 $2$，我们可以把 $2$ 和 $1$ 染成不同颜色来构造合法方案。

首先暴力其实和正解没啥关系，暴力是你考虑 dp 设 $f_{i,j}$ 表示前 $i$ 个划分两个序列，一段结尾是 $i$，另一段是 $j$ 的方案，可以维护到值域线段树，对于每个左端点复杂度为 $O(n\log n)$，时间复杂度 $O(n\log^2 n)$。

考虑如何计算一个区间的贡献，我们把 $i a_j$ 的 $i,j$ 连边，表示他们之间不能相同颜色，此时需要图构成一个二分图，而染色方案即为 $2^{cnt}$，$cnt$ 表示连通块数量。

考虑对右端点 $r$ 进行扫描线，加入 $r$ 时考虑对于每个左端点 $l$，其构成的区间内连通块所产生的贡献产生多少影响。考虑找到最大的 $j < r,a_j < a_r$，同时找到最大的 $k < j,a_k > a_r$，考虑对于 $l$ 的贡献可以分为三类：

• $l \in (j,i)$，此时由于 $j$ 是左边第一个 $a_i$，最终都会把整个区间合并成一个连通块，所以不用算贡献，直接赋值成 $2$ 就好了。
• $l \in (k,j]$，此时同样只有 $j$ 右边的数会与 $i$ 合并，设 $k = i - j - 1$，则贡献为 $2^{1-k}$。
• $l \le k$，此时会把一个连通块与 $i$ 合并，并把 $j$ 右边的合并上去，贡献为 $2^{-k}$。

要注意上面我们并没有去掉不合法情况，考虑哪些区间是不合法的，维护 $L_i$ 表示最大的 $l$ 使得 $[l,i]$ 合法。考虑 $l < L_i$ 的区间都是不合法的，区间赋值成 $0$ 即可。

而 $L_i$ 是好求的，维护每个点前面第一个大于它的位置，值域树状数组可以求出 $L$。

而上面我们只解决了单个区间的贡献，也就是右端点为 $r$ 时每个左端点的贡献，想要求出 $l \in [L,R]$ 还需要维护历史和，线段树维护即可。

T4，首先不考虑最终图能不能是一条欧拉回路，假设现在我们对于每个点 $u$ 的所有出边 $w_1 \le w_2 \le \dots \le w_{2k}$，如何给边两两配对做到最小代价，你发现一定是 $1\to 2k,2\to 2k-1\dots$，但这样配对后产生的路径可能是若干个环而不只是一条欧拉路径。

考虑调整需要我们更改一些配对，从而使得所有配对形成一个欧拉路径。假设我们已经确定了一个配对贡献的上界 $P$，则 $i < j$ 的两对配对交换合法的条件是 $w_j + w_{2k - i + 1} \le X$，同时你发现若 $i,j$ 可以交换配对，则 $i,j$ 之间这段区间内任意相邻两对均可以交换配对，于是只需要考虑相邻交换的情况就可以覆盖全部交换方案。

把原图中的边看作点，初始的配对看作边，考虑现在形成了若干个连通块。任意两个连通块之间想要连通，就需要交换其中的两组配对，由于我们只需要考虑相邻的配对就可以覆盖所有情况，于是我们把相邻的配对看作是一条边，边权为这次交换的代价，对这张新图做 Kruskal 即可，时间复杂度 $O(m \log m)$。

打个 CF 还能给号打封了。。。

#1118. 【UER #14】果冻

昨天没写这个题，今天写一下，现在暂时只会一个 $\frac{3}{2} n\log n + n$ 的做法，操作次数大约在 $6500$ 左右。

首先由于是由排列生成的序列，每对 $\{x,n+1-x\}$ 只会出现两次，考虑有哪些能够利用的信息。如果把极差是否为 $k-1$ 看作状态 $p$，则操作前后 $p$ 是否变化可以让我们确定选择的集合中有几个 $\{1,n\}$。

考虑可以通过二进制分组，每次询问该位为 $1$ 的编号的集合，我们可以确定出两个 $\{1,n\}$ 对的位置的异或。取出两者差的某一位，钦定 $u$ 该位为 $0$ 而 $v$ 为 $1$，考虑接下来选出的集合要求该位均为 $1$，我们就可以确定出 $u$ 进而确定 $v$。

这样我们通过 $2\log$ 次确定了 $\{1,n\}$ 的位置。

考虑当确定下位置，我们就让这些位置均把较小值放在 $A$ 序列，接下来有什么能用的信息？

考虑极差这个信息可以告诉我们最大值，设极差为 $t-1$，则当前处理 $\{t,n+1-t\}$，我们通过一次操作只能知道操作后是否有 $n+1-t$ 位于 $A$ 序列，于是每次需要 $2$ 次询问才能知道一个集合内有几个 $\{t,n+1-t\}$，剩下的就和上面一样，找到两者不同的位还原即可。

最终同样需要操作，使得这个对中较小的数位于 $A$ 序列中。

10.16 图论专题？杂题？

P6329 【模板】点分树 / 震波

点分治哦哦的耶！

点分树板子，考虑建出点分树后，我们可以通过 $x$ 在点分树上的祖先覆盖到 $x$ 通往子树外的每一条路径，我们希望维护距离 $x$ 不超过 $d$ 的点权和，考虑建出点分树，对每个点树状数组维护距离不超过 $k$ 的点权和。

考虑每次需要被算到的应该是 $fa$ 的子树去掉 $u$ 对应的这棵子树，于是需要记录 $pre$ 表示 $u$ 子树是哪一棵。但我们并不能直接减去 $pre$ 子树内不超过 $k-1$ 的数量，因为点分树修改了树的形态，$u$ 与 $fa$ 距离并非 $1$。

首先第一个需要注意的就是点分树上距离并不是深度差，点分树上 $u$ 和 $fa_u$ 之间距离也不是 $1$，于是我们需要同时维护第二棵树状数组表示到 $fa_u$ 距离不超过 $d$ 的点权和。

然后就没啥了，注意树状数组要动态开，每个点只需要 $O(siz)$ 的空间，否则复杂度是错的。

唉，好像今天就只做了这一个题，好摆，唉。

哦看了个核桃模拟赛但是，哎没做啥难题，只会做简单题，所以不放了。

10.17 模拟赛

要 CSP 了，说实话，很期待啊。真的很期待啊。

T1，读错题了但问题不大，你发现一次操作实际上是在差分序列上前缀 $+1$，并把 $k+1$ 位置 $-k$，由于后面操作会影响前面，于是从后往前维护当前能够进行的操作次数，贪心即可。

T2，怎么也读错了，考虑题目要求从前往后依次放，首先一段区间 $[l,r]$ 需要单调不降，其次需要满足 $[1,l-1]$ 不存在 $x \in (a_l,a_r)$，否则贪心尽可能长的覆盖一段即可。

T3，首先想到可以求出每个点走到 $S$，$T$ 的最小值 $d_i$，因为前面走尽可能小是最优的，但你发现后面我们需要的是从 $S$ 的出边 $\ge$ 某个值的所有路径中，找到终边最小的。

考虑直接做是很困难的，同时想要维护出所有的路径也是不现实的，你发现没太有办法压缩路径数量，于是考虑能不能类似把边看成点的方式，用某些操作重新建图。

考虑记录点 $(i,w)$ 表示走到点 $i$，当前时间为 $w$，则首先可以在一个点一直等待，因此对于每个点连的所有边，它们之间的 $w$ 互相连边。

同时考虑原本的出边 $i \to j$，你发现可以看作是 $(i,w) \to (j,w)$ 连边，此时可以对于每个 $(t,w)$ 维护出从 $S$ 出发到达 $(t,w)$ 的所有路径中，起点的最大值 $mx_t$，询问只需要二分最大的 $w$ 满足 $mx_t \ge d_i$。

10.18 杂题

CF

E，首先考虑一个 $O(n^2)$ 的做法，首先你可以发现答案是原括号序列合并若干个 ( 得到的，同时考虑一下前面能否接上操作得到的新的串。

考虑枚举选择的 ( 串的右端点，一个暴力的做法是每次暴力向左跳，考虑若左边是一个 ( 则直接跳过去即可，否则是一个 )，我们找到与它配对的 (，设位置为 $p$，则我们跳到 $p-1$ 的位置，相当于把中间这段删除，代价为 $\frac{len}{2}$。

考虑暴力跳太慢了，于是倍增维护这个跳的过程即可。

D2，假设每个区间有颜色，我们实际上是要求任意两个位置，覆盖它的颜色集合不完全相同，这样我们就可以区分出这两个位置。

考虑首先按照初始给定的区间求出每个位置的颜色，划分极长连续段使得每段内不存在相同颜色（这里颜色指的是每个位置的颜色集合），则该连续段内两两元素需要互相区分。你发现加入一个区间 $[l,r]$ 可以帮助我们区分 $(l-1,l)$ 和 $(r,r+1)$，设共有 $X$ 个连续段，则选择的区间个数下界为 $k = \lceil\frac{X}{2} \rceil$。

考虑首先找到各个段的端点，若只有奇数个，我们可以添加一个端点 $n$，因为重复的端点是没用的，相当于新加了一个空的极长连续段。

现在有偶数个端点，我们把他们两两配对就可以选出若干个区间，因为选的是极长不同段，于是在这些段内添加端点而区分 $i,i+1$ 是没有意义的，我们希望尽量充分利用这些端点。

设这些端点为 $p_1 \le p_2 \le \dots \le p_{2k}$，有一种构造方式是 $(1,k+1),(2,k+2)\dots$ 这样子配对，你发现这样可以使得任意两个原本连续段，覆盖他们的新区间集合互不相同，设这些新区间颜色为 $1,2,\dots,k$，则每个段加入的颜色实际上是

$$\{1\},\{1,2\},\{1,2,3\},\dots,\{1,2,\dots,k\},\{2,3,\dots,k\},\dots,{k}$$

后面好像有点问题，好像我做麻烦了，可以更简单。

场上我的想法是，需要找到端点数最少的起点终点，所以需要首先倍增维护跳的过程然后求最小操作次数，找到最小终点，但事实上只需要以 $1,n$ 作为起点终点，若 $1,n$ 两端集合不同则在中间再添加一个端点即可，这样不需要倍增，很简单的做法。

这样做的依据在于，所有端点均在第一段和最后一段的端点之间，反证法证明不存在非法情况即可。

#22880. Guess the Graph

哎感觉做这种题，就是会有很强的挫败感，尤其是好像我绝大多数时间都没有独立做出题，而独立做出的题又，不会给我很大的成就感。其实很多时候已经很接近做出来了，但是就是，没有发现一些东西。

首先你发现这东西比较刁钻，能得到的信息是非常少的，直觉上我们几乎需要每次询问的两个集合区别只在选不选 $u$ 上，设 $f(S)$ 表示 $S$ 集合的割的大小，则 $f(S \cup u) - f(S) = deg_u - 2 \times cnt$，其中 $cnt$ 表示 $u$ 与 $S$ 集合内点的边数，我们记录 $F(S)$ 表示这个差。

考虑把点排成一个序列，可以二分答案找到 $f$ 从 $>0$ 变成 $\le0$ 的位置，则该位置上的点一定在集合内，并且你发现加入一个 $u$ 的邻居会对集合的 $F$ 造成 $-2$ 的代价。

于是 $F$ 具有单调性，可以通过二分答案找到这个位置，此时考虑 $F(p-1)$ 和 $F(p)$，会有 $2,0$ 和 $1,-1$ 两种情况，分讨一下，然后对每个位置进行一次询问就可以确定出它是否位于集合内。

P17723 [SCP-S 2026] 函数 / func

首先有一个发现是只有 $\text{mex} = 2^k$ 时他才可能会有贡献，否则一定可以通过小的凑出来，我们把贡献拆分成 $\text{mex}$ 带来的贡献和普通位带来的贡献分开计算。

考虑枚举由 $\text{mex}$ 带来的贡献，首先要求区间内不存在 $x$ 满足 $x$ 的第 $k$ 位为 $1$，否则该贡献可以算到 $x$ 上，我们根据这样的位置把序列划分为若干段，则 $\text{mex}$ 能贡献到的区间不会跨过这些位置。

于是可以枚举 $\text{mex}$ 计算贡献，考虑当前对 $[L,R]$ 内的区间计数，双指针可以维护出区间 $[L,R]$ 内 $\text{mex} = k$ 的最小区间，考虑让每个合法区间被其中第一个 $\text{mex} = k$ 的子区间算到，于是找到这些区间的左端点从小到大排序设为 $L,l_1,l_2,\dots,l_k$，每个小区间可以贡献的左端点为 $ql\in [l_{i-1} + 1,l_i],qr \in [r_i,R]$，计算贡献即可。

对于原序列中数的每个位产生的贡献可以用类似的方法算出，时间复杂度 $O(n\log n)$。

10.19 杂题

#22884. Idols and Fans

考虑把每条无向边 $(u,v)$ 看作是物品，则每个点 $u$ 向它的出边表示的点连接一条边，问题转化为二分图最小权匹配问题。但这题有一个非常好的性质是右部点度数 $\le 2$。

先来考虑如果没有二元环的限制要怎么做，每个元素直接选择边权最小的一条出边即可，考虑若在这个过程中出现了二元环 $u,v$，则说明这条边同时作为了 $u,v$ 的最小值，于是 $u,v$ 中必然有一个点选择了这条边，设 $u \to v$ 边权为 $a$，$v \to u$ 边权为 $b$，我们首先把答案加上边权 $a+b$，考虑把 $u,v$ 中一个替换一条出边，我们可以直接合并 $u,v$ 的出边集合找最优方案，合并时把 $u$ 的出边 $-a$，$v$ 的出边 $-b$，然后合并不断处理非法方案即可。

可以使用可并堆维护。

神秘题？

给定一棵树，第 $j$ 条边的编号为 $j$，$q$ 次询问 $l,r$，求出只保留 $i \in [l,r]$ 的点和边，有多少个连通块。

$n \le 10^6$。

考虑如何降维，需要求的是连通块数量，由于原图是一棵树，删掉若干点和边后会变为森林，从而有性质 $cnt = |V| - |E|$，而点数就是 $r-l+1$，只需要计算边数。

看上去边数的限制好像是 $l \le i,u_i,v_i \le r$ 的三维偏序，但实际上我们可以定义 $L_i = \min(i,u_i,v_i)$，$R_i = \max(i,u_i,v_i)$，此时问题变为二位偏序，扫描线树状数组即可解决，时间复杂度 $O((n+q) \log n)$。

这是啥比赛

哈哈哈说实话题倒是还可以哦，除了这个 T3 我没有做。

T1 没啥好说的，一眼看上去可以线段树优化 dp，再看看发现转移的左端点是单调的，可以单调队列优化 dp，然后就做完了。

T2 是一个非常不错的题啊，你发现直接计数是没法做的，同时想要预处理某些东西或者直接上数据结构维护是非常困难的，但事实上，考虑固定右端点，伴随着左端点从小到大变化，$d$ 逐渐变小而 $g$ 逐渐变大，考虑对于每个固定的 $r$，满足 $d \ge g$ 的左端点应当是一段前缀，从而我们可以计算出 $d \ge g$ 的区间数量。

同理计算出 $d \ge g$ 的区间数量，两者相减即可得到答案。

T4 咋感觉比这个 T2 还简单啊，感觉我也不知道咋想到的，应该是你发现所有点向上移动一层会把贡献取反，直觉上发现可以对于每个 $u$ 记录当前子树内最顶上一层点的贡献，考虑设 $f_{u,x}$ 表示以 $u$ 为根的子树，当前最顶上一层对父亲贡献为 $x$ 的方案数。

首先记录一个 $h_x$ 辅助转移，有 $h_x = \sum\limits_j f_j \times h_{x - j}$，考虑点 $u$ 是否要选作为关键点，若选则有 $f_{u,1} = h_{1}$，对于剩下的不选的情况，有 $f_{u,x} \leftarrow h_{-x}$，加个偏移量，上下界优化可以做到 $O(n^2)$，答案为根的 $h_1$。

10.20 模拟赛

这场模拟赛原来搬的是 ICPC 西安，感觉题的质量都还不错啊，没有很烂的题，可能真的是选手的问题吧。

T1，H。

很不错的一个题，考虑直接枚举不太现实的，而也没有特别好的别的想法，那肯定是可以减少枚举量，比如发现一些单调性或者啥的，或者枚举量只与某些东西有关。

考虑如果已知了要用 $k$ 个金属化，那么覆甲的次数是可以从前往后贪心算出来的，同时你可以观察到这个次数实际上是一个只与 $i$ 和 $k$ 有关的，于是维护一个 $c_i$ 表示与 $i$ 相关的贡献，你发现 $k$ 的贡献取决于 $\le k$ 的 $c$ 的数量，于是只需要枚举这些值即可。

T2，G。

感觉同样是一个很不错的题，确实没想到。

把操作看作是对一些数 $-1$，我们要最小化操作次数把所有数降到 $0$。

首先你要想到把字符串放到 trie 上，此时考虑一个 $\oplus k$ 操作长什么样，你发现对于每个节点的两个儿子，要么操作其中一个散段，要么操作一整段 + 一个散段，并且我们可以通过改变异或的值任意选择操作的散段。

于是就操作就非常的宽泛了，我们只需要记录操作的散段和整段的次数。但这个状态数仍然非常大，考虑如何优化状态数，你发现换掉一个散段一定是不劣的，因为散段必须单独进行一次操作，而整段可能会在向上合并过程中变成散段，但它可以合并。

而且你发现散段数量不是越少越好，因为可能可以在上面的层中合并两个整段，从而避免产生新的散段，于是我们维护 $(x,l,r)$ 表示最小散段数、在最小散段数的前提下整段数可以取到的区间，考虑向上合并过程中如何拼一拼更新这个三元组即可。

T3，D。

哎，不容易，做出来了，题其实挺好的。

首先这个好区间有性质：好区间的交还是好区间，好区间分别去掉交的部分还是好区间。

于是找到最大的 $y$ 满足 $a_y = 1$，找到最小的 $x$ 满足 $b_x = 1$，此时有 $a_{x-1} = 1$，$b_{y+1} = 1$，扩展一下，你发现对于 $i\in [x,y]$，这些 $a,b$ 都满足这样的限制。

设 $B_i = b_{i+1},A_i = a_i$，此时我们找到了 $x < y$，则满足 $i \in [x,y]$ 都有 $A_i = B_i$，考虑如何构造这样的方案。

首先对于 $[1,x-1]$ 的前缀，$b$ 只会是 0 或者 ?，你发现如果 $b$ 都是 0 我们可以给出对应构造，于是直接看作 0 就好了。对于后缀同理。

中间部分，由于两边近似相同的关系，我们可以维护当前值域最大值，进行构造，举例子说吧，比如一个 $110011$，我们可以给出构造 $124536$，这样正反都是对的，所以就完成构造了。

剩下的情况是 $x \le y$，分讨一下就行了。

hhh 感觉，选手确实不应该对题目出成什么样的区分度，有要求，我觉得不要出纯脑电波题或者纯，想到一个结论然后把它包装一下变成题，就足够了，至于区分度或者随机取分的问题，我觉得考验的就是选手的硬实力以及，对于这套题的适应程度。

毕竟我觉得肯定有些人就是希望，区分出某种意义上的绝对实力，但确实也要，给一些人一些翻盘的机会不是吗。

#8240. Card Game

哎，好题题单里选出来的，好像真的确实是好题哦。

考虑设 $f(l,r)$ 表示初始区间为 $[l,r]$ 时的答案，考虑这个东西要如何算，你发现好像很困难。不妨只观察 $l - 1$ 的位置，考虑什么时候这个位置会被删除，以及删除后会对后面的哪些位置产生什么样的影响。

记录 $nxt_x$ 表示下一个 $a_x$ 出现的位置，考虑 $l$ 这个位置只会在 $nxt_l$ 被删除，于是若 $nxt_l > r$，则 $l$ 永远不会被删除，且不会影响到后面的。否则你发现我们并不在乎 $[l,nxt_l]$ 这段具体是怎么删的，因为一定会在 $nxt_l$ 被删空。

此时可能会有想法是我们递归的去考虑，那么你可以考虑 $f(l,r)$ 的转移：

• 若 $nxt_l > r$，从 $f(l+1,r) + 1$ 转移。
• 否则从 $f(nxt_l + 1,r)$ 转移。

好像还没思路，我们把 $f_l(r)$ 看作一层状态，你发现状态的转移只会从第 $l+1$ 或第 $nxt_l+1$ 层转移过来，且修改是极少的，考虑使用主席树维护下每层的状态，转移时只需要将 $nxt_l+1$ 层的 $O(\log n)$ 个区间接上来即可。

所以其实感觉今天效率很低的，下午好像就看懂了个 T2 的题解，也没干成啥别的事情，好像一直在做很多没有任何意义的事情，比如想要选题然后感觉不喜欢的就全扔掉最后什么也没学到。

10.21 贪心，杂题

AT_arc228_b [ARC228B] Minimize Topological Order

这个转化还是挺厉害的，考虑字典序最小对于这棵树的限制，找到 $i$ 前面最后一个 $a_j > a_i$ 的 $j$，则 $i$ 的父亲在 $[j,i)$，否则可以先选 $i$ 再选 $j$ 使字典序更小。

问题转化为有若干个区间，每次可以选择区间内一个点的 $c_i +1$，要最小化贡献。貌似区间没有性质的话并不好做，只能费用流，我们来观察区间的性质，发现区间是要么不交要么包含的，于是可以按右端点从小到大贪心，然后就做完了，线段树维护区间最大增量，单点修。

#22910. 又一道纸笔问题

考虑首先可以得到一个 $\sum a_{i,j}$ 的下界，考虑哪些操作是可以省去的，你发现只需要考虑相邻两列之间的操作合并，最终答案为总数减去合并数量，而合并数量可以由一次从上向下扫描解决。

P14638 [NOIP2025] 序列询问

哦哦的耶，其实一直都想要来做这个题来着，之前感觉看题解都没看懂，感觉有了 GPT 大哥就是 nb。哎说实话，那感觉这题也没那么难。

首先对于一个固定的 $L = R = d$ 我们可以有一个 $O(nq)$ 的做法，记录 $s_i$ 表示前缀和，于是可以预处理出 $b_l = s_{l+d-1} - s_{l-1}$，表示以这个点作为左端点的贡献，于是对于每个 $i$ 需要维护的是 $[i-d+1,i-1]$ 这段区间的最大值，可以单调队列做到 $O(n)$。

接下来考虑假如给定了一次询问 $[L,R]$，对于一个 $l$ 它的 $b_l$ 能取到的右端点同样是一段区间，类似的可以使用单调队列维护出 $b_l$，但此时问题在于，当 $l \le i-L$，我们无法得知 $i$ 是否被包含在区间内，换言之我们不清楚 $b_l$ 取到的最优右端点是否能覆盖 $i$。

但你发现对于左端点 $l \in [i-L+1,i-1]$，该区间必然包含了 $i$ 这个位置，同理对于一个右端点位于 $[i+1,i+L-1]$ 同样也必然覆盖到这个区间，于是我们已经会了如何处理 $R \le 2L$ 的询问，可以通过 $O(n)$ 求出这样的询问的答案。

那么对于 $R > 2L$，一个想法是我们每次把整个询问值域划分为 $\log$ 个段，对每个段都可以按照上面的方法用 $O(n)$ 求出答案，这样我们做到了 $O(nq\log n)$，但貌似没有特别大改善。

事实上没有必要每次重新划分段，我们直接把整个序列划分为 $[1,1],[2,3],[4,7],\dots$ 的若干段，对于每段求一遍答案，此时每个数都可以通过 $O(\log)$ 段求出所有答案，而对于一次询问可以直接把询问的区间拆成整块和散块，整块使用 ST 表维护，散块 $O(n)$ 做一遍，复杂度 $O(nq)$，但感觉常数就很大的样子，说不定还不如直接枚举它跨越了哪些区间然后暴力 $O(n)$ 做。

感觉需要卡常，等会写下代码。

P14637 [NOIP2025] 树的价值

感觉正解，只看懂了一半啊，所以先写一下 $O(nm^2)$ 做法吧。

首先有一个 $n^3$ 的做法是直接设 $f_{u,j,k}$ 表示 $u$ 为根的子树，$mex = j$，当前有 $k$ 个填了 $> j$ 用于贡献给后面的数，后面可以随时用他们来增加 $mex$，考虑转移的时候新的状态是 $\max$，我们直接前缀 $\max$ 优化掉可以做到 $O(n^3)$。

考虑一些性质，首先每个点会选择其一个儿子的 $mex$ 继承过来，并会在该位置选择填 $mex$ 来让自己的 $mex + 1$ 或者选择贡献给后面的某个东西。

考虑如果把继承关系看作是父亲选择一个儿子连一条边，我们实际上通过继承关系进行了一次树的链剖分。且点 $u$ 的贡献实际上是找到它选择的这个值第一次产生贡献的祖先 $x$（可能存在 $x = u$），贡献的值实际上是 $x \to top(x)$ 这段继承链的长度。

于是发现我们希望每个点尽可能贡献给到根路径上一段尽可能长的链，考虑在 dp 过程中改成维护到根最长链以及当前链长度，这样有了一个 $O(nm^2)$ 的做法。

优化在于优化一下状态数，使用更少维度表示出所有状态，还没看懂。

10.22 模拟赛

怎么说，可能，算了不说了，可能能够做题还是挺舒服的，感觉推一个题的过程，是很舒服的。

T1，考虑每个数在最终序列出现的位置是一段区间，我们需要给每个数确定一个位置，然后必须要有一次操作覆盖了 $i$ 和 $p_i$，而最优情况就是你把所有有交的这些区间全都用同一次操作，这样每次操作之间互相不交，显然相交会产生重复部分多余的贡献。

考虑怎么让区间尽可能不交，对于一个 $i$ 假设最终序列 $a_i$ 的连续段长度为 $len$，我们按照原序列中的顺序把这 $len$ 个位置依次分配给每个点。

最后若选出来的不交区间不超过 $k$ 则直接选上就行，否则你需要合并一些区间，合并的代价是两段之间的距离。

T2，首先你发现前后缀 $\max$ 会把整个序列划分为若干段，而每段贡献是独立的，考虑设 $f_{l,r,x}$ 表示区间 $l,r$ 恰好使用 $x$ 次消除的方案数，转移时找一个 $a_i = x/-1$ 的位置 $p$，从 $f_{l,p-1,a} \times f_{p+1,r,b}$ 转移，要求 $\max(a,b) = x$，转移系数为 $r-l\choose p-l$。

考虑 $\max$ 这个东西可以前缀和优化掉，所以这部分可以做到 $O(n^4)$，考虑如何合并信息，你发现全局最大值把前后缀分成了独立两部分，而同时方案与具体值填了多少是无关的，只与大小关系有关，于是我们记录 $pr_i$ 表示 $i$ 的前缀的方案数，你发现我们刚刚的区间 dp 可以计算出两边都有端点的方案数，于是有转移 $pr_i = pr_{j-1} \times g_{j,i}$，其中 $g_{j,i} = \sum\limits_h f_{j,i,h}$，对后缀同样转移，系数乘上分配值域的方案数。

T3，挺难的一个题，但感觉本质是发现性质，然后求出下界再分讨一些边界情况的。

就首先你要发现性质是，只有 01010101 连续段是没法删的，因为只要两个 $1$ 中间没有 0 或者有 $\ge 2$ 个就可以，那你把原序列划分为若干个 $010101$ 段，可以求出一个答案上下界。

然后你要考虑到两端端点的方案，分讨一下就行了，然后只需要维护最大段长和端点处段长以及 $1$ 的总数量。

P17725 [SCP-S 2026] 大雨 / rain

首先显然可以把异或操作差分一下，于是前缀操作可以转化为划分成若干段，对每一段进行操作，使得最终整个序列不降。同时每个端点只会进行一次操作，因为操作是可以合并的。

考虑整个序列单调，可以看作是每一段内部单调，同时段与段之间也保持单调，先来考虑段内单调的限制，一个有用的 trick 是我们可以把这样具有传递性的偏序关系拆到任意两个相邻位置之间，而你发现相邻位置异或一个数之后的大小只与两数异或的最高位有关，也就是限制实际上是某一位是 $0/1$，我们可以从前往后根据这个限制贪心地划分连续段。

现在考虑让相邻连续段合法的限制，首先现在的连续段相邻之间一定是不满足限制的，否则会在划分时把他们合并起来。设共有 $k$ 个连续段，由于没有限制操作的值域，有一个很直接的方法是我们直接根据高低位来限制大小，也就是从后往前从高到低放一堆 $1$，这样需要 $k$ 次操作。

但实际上有可能可以做到 $k-1$，也就是省掉对整个序列的一次操作，此时需要维护的是一个 $y$，使得 $y$ 首先能够符合段内某一位为 $0/1$ 的限制，同时能够使得 $a_{l+1} \oplus y \le d_{l}$，其中 $d$ 表示在最优段数的前提下，前缀最大值能达到的最小值。在满足这两个限制的前提下，我们希望找到 $a_r \oplus y$ 的最小值。

trie 树可以维护，用一些 tag。

P8503 「CGOI-2」No mind to think

挺不错的一个题？

https://www.luogu.com.cn/article/8db0inqj。

T839548 10.25 T2 - 树

煎蛋题，怎么做这么久。

一个想法是菊花可以解决几乎所有情况，首先加入一个点连到根，接下来如果需要 $2$ 就继续连到根，如果需要 $3$ 就从某个连到 $2$ 的点连到根，否则从连到根的点连到 $2$，最后补全 $1$ 即可。

不管了，准备一下打 UER 去了。

10.24 模拟赛

哦哦的耶，UER 打好了哦，舒服了，但是 T4 挂分了，好像是某些极端情况会跑很慢吧。

https://uoj.ac/contest/115

T1，太神秘了，感觉上每次删掉一半就很优，而且好像更大的时候只会不那么优，并且你能够取到 $s-t$ 作为下界，所以就求个 $\max$ 就好了。

T2，考虑贪心一下，你发现可以找到 $1$ 前面是 $0$ 的这些位置，根据这些位置划分连续段，任意两个连续段之间不可能合并起来一起放。

先考虑最后一段连续的 $1$，我们把 $1$ 先与这些匹配，然后再和前面的 $1$ 匹配，最后尝试 $100$ 或者 $00$ 匹配，只需要计算额外花费了多少长度就好了。

T3，还不会。

T4，还不会正解，先考虑一个暴力吧，考虑设一个 $f_u$ 表示从 $u$ 出发染色，$u$ 子树内全部染色好最少需要多少时间，转移需要从小到大排序，设为 $a_1 \le a_2 \dots a_k$，则转移为 $f_u = \max\limits_{i = 1}^k a_i + \lceil \frac{i}{c_u}\rceil$，考虑这样就可以枚举根然后算，复杂度 $O(n^2)$。

考虑换根，你发现换根时会删除掉一棵子树，如何继续维护转移呢，依旧从小到大排序，你发现只是把后面一部分变为 $\lceil \frac{i-1}{c_u} \rceil$，于是前后缀分别维护，合并起来即可。

此时我们已经会求最优的 $T$ 了，考虑一个点最晚要在 $T - f_u$ 的时间被开始操作，而更早并不需要让儿子也跟着提前，因为完全可以等到儿子需要操作时再操作，于是把某个 $u$ 提前 $1$ 的贡献就是它的点权。从而可以按照点权从大到小排序，每个点放入当前还存在的能放的最大位置。

哎，实际上有一个更简单的贪心做法，感觉非常牛啊，而且真的很简单。

做法是这样的：考虑把问题倒过来，设 $f_i$ 表示每个位置出发最快多久能把子树全染好，定义 $d_i = T - f_i$，问题由原来的最大化 $\sum w_it_i$ 变为最小化 $\sum w_id_i$，考虑把正着染色变成倒着染色，或者可以理解成把染色过程倒放一遍。

维护一个队列，队列里存当前树的所有叶子，对于每个 $u$，每轮最多删除 $c_u$ 个它的儿子。对于每一轮我们贪心的删除尽量多的叶子，若产生了新的叶子则它至少在下一轮才能被删掉，最小化删除轮数即可。

且这个做法非常容易做第二问，只需要把维护叶子的队列替换为优先队列，优先删除权值更大的叶子即可。

::::success[证明] 可以用逐轮交换论证证明。只考虑第一问，不考虑点权。

把正向方案倒过来，令 $p_v=T-t_v$。那么：

• 非根点删除时，必须已经没有儿子；
• 同一个父亲 $u$，每轮最多删除 $c_u$ 个儿子；
• 根最后删除，其删除轮次就是 $T$。

我们证明：

每一轮贪心的选择，都能被某个最优方案采用，而不增加结束时间。

假设当前是第 $s$ 轮，存在一个最优方案，与贪心在前面所有轮的删除操作一致。因此，两者当前剩余的树完全相同。

先考虑剩余点数大于 $2$ 的情况。

一、如果贪心本轮没有选中最优方案的根。

设 $u$ 当前有 $k$ 个叶子，贪心任意选择 $$ \min(k,c_u) $$ 个删除。

考虑一个被贪心选中、但最优方案没有在本轮删除的叶子 $v$。设最优方案在第 $t>s$ 轮删除它。

• 如果最优方案本轮在 $u$ 处还有空余容量，直接把 $v$ 提前到本轮。
• 如果容量已经用满，则本轮一定有一个被最优方案删除、但没有被贪心选中的点 $z$。交换 $v,z$ 的删除时间。

第二种情况下，$z$ 也一定是当前挂在 $u$ 上的叶子：因为它能在第 $s$ 轮删除，它的儿子必须在此前已经删完。

交换之后仍然合法：

• 两点的儿子都早已删完；
• 每轮使用的容量不变；
• $u$ 原本要等到第 $t$ 轮之后才能删除，因为原来 $v$ 在第 $t$ 轮删除；所以把 $z$ 延后到第 $t$ 轮也没有问题。

这样不断调整，就能让最优方案本轮采用贪心选出的全部叶子。

二、如果贪心选中的叶子 $r$，恰好是最优方案的根。

这时不能直接提前删除根，但可以换一个根，且不增加时间。

设 $r$ 当前唯一的邻居为 $u$，最优方案中 $$ p_u=t,\qquad p_r=T. $$ 因为原来 $r$ 是 $u$ 的父亲，所以 $$ t+1\le T. $$

现在将根改成 $u$，并设置 $$ p'_r=t,\qquad p'_u=t+1, $$ 其他点的删除时间不变。

这个修改合法：

• $u$ 原来的儿子都在第 $t$ 轮之前删除；
• $r$ 当前已经是叶子，因此除 $u$ 外，它原来的儿子都在第 $s$ 轮之前删完；
• 新增的关系是“$r$ 成为 $u$ 的儿子”，在第 $t$ 轮删除 $r$。原来 $u$ 自己在第 $t$ 轮删除，所以它原来的儿子都不占用这一轮的容量；
• 新根在第 $t+1\le T$ 轮删除，没有增加结束时间。

而且剩余点数大于 $2$ 时，叶子的邻居 $u$ 不可能也是叶子，因此新根不会被贪心本轮选中。

于是又回到了第一种情况，可以继续通过交换，让本轮采用贪心的选择。

三、最后的边界恰好也是最优的。

• 若第 $s$ 轮开始时剩两个点，它们必须一前一后，最早分别在第 $s,s+1$ 轮删除。
• 若第 $s$ 轮删完若干叶子后只剩一个点，这个点刚刚失去儿子，最早只能在第 $s+1$ 轮删除。

贪心都恰好达到这个下界。

因此，从一个最优方案出发，我们可以逐轮把它调整成贪心方案，结束时间始终不增加。所以贪心剥叶得到的 $T$ 一定最小。 ::::

dmy 比赛

T1，考虑按照 $b$ 的位置分段，此时显然不可能同时选到不同段内的 $1$，而同一段内可以全部选上，只需要取到区间的正中间即可，于是对每一段取最大值即可。

T2，ria，原来第一直觉就是对的，但其实也没那么对？这下大了。

考虑直接设 $f_{i,j}$ 表示第一行放了前 $i$，第二行放了前 $j$，考虑第一个想法是记录下最少段数，并钦定 $i,j$ 作为末尾段，但这样转移你需要同时枚举两维下一个位置，甚至于最优也至少需要枚举一个位置，求出另一个位置。

考虑实际上可以记录二元组分别表示段数和最后一段放了多少，段数小的前提下，最后一段放了尽可能少，发现这样是可以筛选出最优信息，因为最后一段更大，就是能放进去也只会持平，最后一段放得少显然更优，转移只需要考虑 $i+1$ 或 $j+1$ 即可。

T3，怎么小朋友都会做这个题，感觉不简单啊。

会了再来写吧。

T4，也是会了再来写吧。

10.25~10.30 杂题

没做杂题，补题了，等会写一下这场 CF，以及晚上还有 ARC？还有一个 KDOI 的比赛也没做。

说实话感觉，这周任务不少啊，一起写吧。

CF2277E Tree Guessing

https://www.luogu.com.cn/article/n031hxzk。

KDOI Tournament 2026 Advanced Round 1

感觉题都是挺不错的题，反正就是，可能喜欢这样的风格吧。

T1，你发现首先 $10$ 是必选的，并且用 $4 \times 10$ 去换一个 $50$ 太亏了，因为换来 $50$ 不会有任何用，所以把 $50$ 替换成 $20$ 一定是不劣的。

于是首先把每个 $20$ 与他前面最近的一个还没匹配的 $10$ 匹配，接下来从前往后扫，维护当前手里能用的钱（匹配了的 $20$ 以及没有匹配的 $10$），能换 $50$ 的就换过来，最终答案为匹配的 $20$ 数量 + $10$ 的数量 + 换的 $50$ 数量，时间复杂度 $O(n)$。

T2，你发现 $c_i \ge d_i$ 的限制是很有用的，这可以保证你在解锁某个点之后钱数不会变少，那只需要从小到大依次解锁，过程中维护当前解锁代价最小的点，这样可以尽可能利用每个点的返现。

用一个 $set$ 维护即可，每次找到最小值把出边全都更新一下即可。

T3，考虑发现一些性质，我们观察每个点的移动，首先考虑这个点会向左还是向右移动，记录 $t_i$ 表示 $(i,i+1)$ 这次交换的时间，也就是 $t_{p_i} = i$，考虑每个点向左或向右移动只取决于 $t_{i-1},t_i$ 之间的大小。

同时我们考虑一个点会走到什么地方，我们以向左走为例，首先要求 $t_{i-1} < t_i$，同时对于路径上每个 $j$ 都满足 $t_{j-1} > t_j$，且终点满足 $t_{k-1} < t_k$。

我们根据 $t_{i-1},t_i$ 大小关系把所有点分为两类，不难发现对于向左走的点，其终点为左侧下一个向左走的点，向右侧同理，于是整个序列应当构成了两个置换环，根据这个可以判断是否有解。

若存在解，由于 $t$ 与 $p$ 构成了双射，问题转化为给定一个环，每个位置有 $s_i = 0/1$ 表示 $t_i < t_{i-1}/t_i>t_{i-1}$，求合法 $t$ 序列方案数。考虑枚举 $1$ 的位置断环成链，然后序列上做这个 dp 就好了，做法就是设 $f_{i,j}$ 表示前 $i$，当前末尾在前 $i$ 个排名为 $j$，转移前缀和优化，时间复杂度 $O(n^3)$。

::::success[code]

#include<bits/stdc++.h>
using namespace std;

#define ll long long

const int maxn = 1003;
const int mod = 998244353;
int n,a[maxn],vis[maxn],up[maxn];
vector<int> cyc[maxn];

void add(int &x,int y)
{
    x += y;
    if(x >= mod) x -= mod;
}

int f[maxn][maxn],g[maxn][maxn];

int calc()
{
    for(int j = 1;j <= n;j++)
        for(int k = 1;k <= n;k++)
            f[j][k] = 0;

    f[1][1] = 1;

    for(int i = 2;i <= n;i++)
    {
        for(int j = 1;j <= i;j++)
            for(int k = 1;k <= i;k++)
                g[j][k] = 0;

        for(int j = 1;j < i;j++)
        {
            int sum = 0;
            if(up[i])
            {
                // t[i-1] < t[i]，原末尾排名 k < x。
                for(int x = 1;x <= i;x++)
                {
                    int nj = j + (x <= j);
                    add(g[nj][x],sum);
                    if(x < i) add(sum,f[j][x]);
                }
            }
            else
            {
                // t[i-1] > t[i]，原末尾排名 k >= x。
                for(int x = i - 1;x >= 1;x--)
                {
                    add(sum,f[j][x]);
                    int nj = j + (x <= j);
                    add(g[nj][x],sum);
                }
            }
        }

        for(int j = 1;j <= i;j++)
            for(int k = 1;k <= i;k++)
                f[j][k] = g[j][k];
    }

    int ans = 0;
    // 枚举 1 在 p 中的位置 pos，即 t[1] = pos。
    for(int pos = 1;pos <= n;pos++)
    {
        if(up[1])
        {
            // t[n] < t[1]。
            for(int k = 1;k < pos;k++)
                add(ans,f[pos][k]);
        }
        else
        {
            // t[n] > t[1]。
            for(int k = pos + 1;k <= n;k++)
                add(ans,f[pos][k]);
        }
    }
    return ans;
}

void solve()
{
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> a[i];
    for(int i = 1;i <= n;i++)
    {
        vis[i] = 0;
        cyc[i].clear();
    }

    if(n == 1)
    {
        cout << (a[1] == 1) << '\n';
        return;
    }
    if(n == 2)
    {
        cout << (a[1] == 1 && a[2] == 2 ? 2 : 0) << '\n';
        return;
    }

    int cnt = 0;
    for(int i = 1;i <= n;i++) if(!vis[i])
    {
        int x = i;
        ++cnt;
        while(!vis[x])
        {
            vis[x] = 1;
            cyc[cnt].push_back(x);
            x = a[x];
        }
        sort(cyc[cnt].begin(),cyc[cnt].end());
    }

    if(cnt != 2)
    {
        cout << 0 << '\n';
        return;
    }

    int ans = 0;
    for(int inc = 1;inc <= 2;inc++)
    {
        bool flag = 1;
        for(int i = 1;i <= 2;i++)
        {
            int sz = cyc[i].size();
            for(int j = 0;j < sz;j++)
            {
                int x = cyc[i][j];
                int y;
                if(i == inc) y = cyc[i][(j + 1) % sz];
                else y = cyc[i][(j + sz - 1) % sz];

                if(a[x] != y) flag = 0;
                up[x] = (i == inc);
            }
        }
        if(flag) add(ans,calc());
    }
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    int c,t;cin >> c >> t;
    while(t--) solve();
    return 0;
}

::::

P17535 [JAG 2026 Summer Camp #1] Sliding Puzzle on Tree

哎，这题很厉害。反正，快要 CSP 了，感觉无所谓了，会做不会做的，哎，就。

首先考虑整张图有什么必要条件，我们先不考虑操作顺序，考虑最终状态与初始状态之间有什么联系，由于每条边必须被操作一遍，设 $d_u$ 表示 $u$ 的度数，则奇度点最终状态会被翻转，从而我们要求奇度点中 $a_u = 0$ 的数量和 $a_u = 1$ 的数量相同。

但你发现这个条件并不充分，继续考虑有什么条件，你发现每个子树内只能进出 $1$，且必须操作 $1$，于是我们要求任意子树中，终止状态石子数量 - 初始数量 $= 1/-1$。

发现这个条件是充要的，且要求 $1$ 的这个值为 $0$，而构造方案也比较简单，只需要让每个点的 $+1$ 和 $-1$ 边交替出现，我们把边看作点，对他们之间连边，定向表示先后关系，你发现实际上形成了一棵树，只需要按照 topu 排序做一遍就好了。

arc233

好难啊，只会做这个 A。

A，其实一上来就大概感觉到要怎么做了，但时间可能大部分用在无效思考上了，感觉可能更应该打表或者怎么样搞一下。考虑 $n$ 是偶数打表发现奇数偶数分别有 $\frac{n}{4}$ 上下取整个，直接询问即可，次数不超过 $\frac{n}{2}$。$n = 2k+1$，划分为 $k$ 组，每组和为 $2k+1$，每组内最多出现一个，首先询问 $[1,k]，$，然后看看前面是有的多还是没有的多，选少的那个询问另一组即可。

接下来还原出了 $A$ 序列，考虑一个性质是集合大小只有可能是 $2,3$，使用 $bitset$ 维护即可。

C，感觉是很好的小清新题。

考虑这是一个动态的过程，我们希望把这个动态的过程转化为静态的判定，从而对判定方案计数。

考虑给每条边赋一个边权 $w$，表示删除这条边时左右的点度数，接下来需要发现一些很厉害的性质：

一个子图是特殊的充要条件是，我们可以找到一种边权方案，使得一个度数为 $x$ 的点周围的边分别被赋值成了 $1,2,\dots,x$，且每个合法的赋值方案恰好与一种合法的子图构成双射。

条件的必要性是显然的，考虑它是否充分，以及是否构成双射。对于一个合法的赋值方案，我们可以按照边权从大到小依次删掉边，就能够得到合法方案，于是条件是充分的。

考虑赋值方案是否与合法子图一一对应，你发现对于任意一个合法子图，我们可以从叶子开始，叶子与父亲之间边权显然为 $1$，对于剩下的点从下往上做，每次每个点连向儿子的边一定都已经被确定好，只需要根据限制填它到父亲这条边即可。

由此我们也得到了一个 dp 思路，考虑设 $f_{u,k}$ 表示考虑了 $u$ 的子树，$u$ 到父亲的边权值为 $k$ 的方案数。任意选取根，钦定每个子图被深度最浅的点统计到。

考虑如何转移这个 dp，考虑一个暴力转移是，我们直接记录 $g_S$ 表示子树内已经选出了一些边，他们的边权集合为 $S$，此时的方案数。转移 $g$ 很简单，只需要考虑 $v$ 是否要选即可。

思考 $k$ 能取到的上界，实际上只有 $\log siz$，首先你手模一下就会发现限制是非常严的，对于一个选择 $k$ 的点，必须连接了 $1,2,\dots,k-1$ 的点，考虑用一个式子来表示：

$f(1) = 1,f(x) = 1 + \sum\limits_{i=1}^{x-1} f(i)$，邻项作差，发现差值恰好为 $f(x) - f(x-1) = f(x-1)$，即有 $f(x) = 2f(x-1)$，于是 $k$ 只能是 $O(\log n)$ 的级别。

感觉上均摊一下，可以分析到 $O(n\log^2 n)$ 的复杂度，考虑转移，枚举 $k$，要求集合为大小至少为 $k$ 的前缀，于是有 $f_{u,k} = \sum\limits_{t=k}^T cur_{{2^t - 1} \oplus 2^k}$，其中 $T$ 表示上界。

考虑统计答案，枚举前缀大小，答案为 $\sum\limits_{k} cur_{2^k - 1}$。

#20737. Interval MST

非常厉害的一个图论题，选手不会做，选手不会做，选手不会做。

首先考虑一个 $O(nq)$ 的做法，对于每个询问我们需要用 $O(n)$ 的时间求出答案。

考虑一个区间的答案如何求出，首先我们不难做到一个 $x_r - x_l$ 的上界，只需要把相邻两个点连边，加减消一下就能做到这个上界。

考虑接下来能不能做到更优，你发现有些点更换连边可以做到更优，先来考虑最简单的三个点的情况，你发现中间点的收益可以做到 $c_i = \min(0,x_i - mx_i,mi_i - x_i)$，其中 $mx$ 和 $mi$ 分别表示前缀最大值和后缀最小值。

考虑尝试让每个点都取到这个最优收益，也就是我们尝试把一个区间的答案做到 $x_r - x_l + \sum\limits_{i\in(l,r)} c_i$，接下来要做什么呢，我们需要证明这个东西是下界并且给出构造。

这一步就需要选手有极大的勇气相信自己的直觉并愿意花费时间给出证明、有极大的自信能够做出了这个问题、有极强的实力预留出充足的时间来做这道题。

首先来说明这个是下界，考虑任意一个方案，找到该方案上从 $l$ 到 $r$ 的一条链，不在该链上的点其能取到的最优贡献显然就是 $c_i$，对于链上的一些边，我们把他们分为正向和反向的边，正向边的总贡献显然为 $x_r - x_l$，我们只需要说明反向边的贡献不优于 $c$。

而由于反向边每条边都是右边减左边，而左边的数显然不优于前缀最大值，于是反向边贡献显然不优于 $c_i$，于是我们证明了这个式子是答案的下界。

同时尝试说明我们能够给出一组合法的构造达到这个下界，首先找到 $c_i = 0$ 的所有 $i$，这些 $i$ 的位置满足前缀均 $\le x_i$ 且后缀均 $\ge x_i$，于是我们可以根据这些点把整个序列划分为若干独立段，每段内取到的前后缀最大最小值只可能在本段内取。

考虑一个段 $[a,b]$，首先连一条边 $(a,b)$，接下来里面的边就根据最优策略连，此时整个区间有 $b-a+1$ 个点，$b-a$ 条边，含有 $(a,b)$ 的连通块是一棵树，而其它的连通块是若干个环，且贡献已经为 $x_r - x_l + \sum c_i$，我们希望在不修改边数、不修改贡献的前提下把这若干个连通块连通。

这是容易的，我们从每个连通块任取出一条边 $(x,y)$ 满足 $x

于是得到了一个 $O(nq)$ 的做法，只需要每次暴力处理前后缀最大最小值即可。

考虑如何优化，由于需要同时维护前缀最大和后缀最小，感觉上这东西没法扫描线，考虑有没有什么其它处理方法。使用线段树，线段树每个节点维护当前区间内的答案，也就是前后缀最大值只取在当前区间内，计算贡献。

考虑一个询问，把它划分为 $O(\log)$ 个完整区间，每个区间内已经有了基准贡献，我们需要看 $[l,L)$ 这段内是否有能够使得区间内的点取到更优的贡献，经过一些转换后这是一个二位数点的形式，可以使用扫描线树状数组维护，由于每个询问有 $O(\log)$ 个区间，于是总的时间复杂度应当是 $O(q\log^2n)$。

CF2272

A，考虑前缀 $\text{mex}$ 单调，于是我们希望最大化第 $n-k+1$ 项，只需要看这个前缀交换两个位置能不能变得更大。

B，被骗了啊，注意到答案就是总数量对 $2$ 取模的结果，然后就做完了，真是神了，如何注意到。

C，考虑直接二分答案，要注意题目没有要求必须是连续段，只要求不存在孤立的黑点，于是优先考虑能不能用一个点连接两个孤立的黑点，如果不能那就只能给孤立点单独分配。

D，头一次秒 D 题啊，我咋这么厉害。

首先加边显然无法使得独立集变得更大，于是考虑做到上界与原来相等。第一想法就是最大独立集 = $n -$ 最小点覆盖，而我们只需要找点覆盖上的点加边，这样新加的边都不会使得点覆盖变得更大。

但这个还是太麻烦了，其实可以直接做，找到一个叶子节点 $u$，钦定 $u$ 一定在最大独立集里，否则我们只需要把它的父亲替换成它，不影响独立集大小。然后只需要把其它连通块全都接到它的父亲上就行了，这样不会影响各个的独立集。

F，因为比较喜欢树上问题和这种比较偏交互、博弈之类的题，所以先开了 F。事实上这是一个不难的题。

先来考虑菊花的情况，你发现菊花的情况只取决于它的度数，这个乍一看其实没啥用，那么继续思考有什么性质。首先发现祖先走过来之后我们不关心祖先那边树到底长啥样，因为祖先已经走过了只能被删掉。

一个想法是尝试设一个 $f_u$ 表示 $u$ 有一个祖先只能被删掉，从 $u$ 作为根，先手必胜还是必败。首先叶子节点的贡献是好算的，考虑如何转移，记录 $cnt$ 表示 $\sum\limits_{v \in son(u)} [f_v = 0]$，则只要 $cnt > 0$，就可以一步走到先手必败，$f_u = 1$。

否则只能根据 $u$ 度数的奇偶性判断。

考虑先随便确定一个根，然后如何换根，你发现删除一个子树只对 $cnt$ 产生影响，于是只需要在换根过程中维护一下这个 $cnt$ 就做完了。

E，其实是简单题。

首先发现 $s,t$ 是一样求的，只需要考虑求 $s$ 的就行，假设 $s_i =$ R，考虑它输出的数是 $s$ 还是 $t$ 贡献过来的：

• $s$ 贡献的，记录上一个 W 的位置为 $p$，则可以通过调整前后把 $t$ 任意多个放在它前面，于是可以贡献 $[p,p+m]$。
• $t$ 贡献的，假设这个位置为 $q$，此时假设 $s$ 中有 $a$ 条在它前面，则有 $a \in [p,i-1]$，可以贡献 $[q,q+a]$，你发现如果存在 $p$ 则这个区间会被 $p$ 的贡献完全包含，因此只需要算不存在 $p$ 的，此时考虑每个 $q$ 的贡献是否有交即可，拿个桶前缀和随便维护一下就行了。

G，考虑把区间转化为 $l-1\to r$ 的一条连边，把边看作无向边，你发现对于一个连通块，其贡献为 $siz - 1$，考虑每次进行单点修改，我们把所有询问离线下来，在时间维上每条边出现是一段区间，可以使用线段树分治维护，时间复杂度 $O(n\log^2 n)$，两个 $\log$ 分别在线段树和可撤销并查集。

云斗 CSP 模拟赛

T1，考虑每个位置能贡献到的系数，端点处只能贡献 $n$，其余位置为 $2n - 2i + 3$，考虑把点权排序，同时把每个位置的系数排序，从大到小依次匹配即可。

T2，首先不难发现 $f=1$ 的边构成若干个连通块，此时修改边相当于合并两个连通块，假设大小分别为 $x,y$，合并的贡献为 $2xy$。

于是希望贪心从大到小合并，但你发现这个问题并不太有法做，幸运的是观察数据范围不难发现 $k\le 2$，只需要考虑两条边是否有公共端点，对于有公共端点，枚举这个端点并取贡献最大的两条边，否则两条边没有公共端点，则贡献最大的一条边的两个端点一定被选中，只需要找除去这条边最大的。

可能还需要考虑最大边是 $u,v$，然后选两条边分别有端点 $u,v$？反正这种情况也是简单的，而且不优于以其中一个为公共端点的情况吧，所以不需要考虑。

T3，首先观察到对于一个静态的局面，我们有一个暴力，是枚举选出边的最大值，此时一定是取 $\le$ 它的最大的 $k-1$ 条边，判断他们的和是否合法。

你发现实际上是在每个时间点，我们希望求出当前最靠右的一个合法长度为 $k$ 的窗口，考虑不断加入时这个窗口的位置是单调的，但加入是不好做的，我们考虑把加入看作是删除，并维护过程中最右边的窗口。

考虑一个删除操作的贡献，若删除的点不在当前的窗口内，则对当前位置不会产生影响，否则把窗口左端点向左移动，找到第一个未被删除的位置，判断当前有右端点是否还能够成为合法端点，若不能则向左移动右端点，然后继续判断即可。

由于右端点单调，左端点同样单调，每个位置只会成为一次左/右端点，总复杂度是 $O(n)$ 的，使用链表维护，时间复杂度 $O(n\log n)$，瓶颈在于排序。

T4，首先考虑一个 $O(n^3)$ 的做法，考虑类似 NOIP T3 的做法，我们设 $f_{i,j,k}$ 表示前 $i$ 个，$\text{mex} = j$，当前有 $k$ 种 $> j$ 的数还没有决策具体值，此时的方案数。要注意状态里延迟决策的是未确定的数的种类数，而不是位置数。

如何转移，考虑下一个数填什么：

• 填一个 $< j$ 的数，可以有 $j$ 种方案，转移到 $f_{i+1,j,k}$。
• 填一个之前出现过的 $> j$ 的数，有 $k$ 种方案，转移到 $f_{i+1,j,k}$。
• 填一个之前未出现过的 $> j$ 的数，延迟钦定它的值，转移到 $f_{i+1,j,k+1}$。
• 填 $j$，此时需要考虑新的 $\text{mex}$，设其为 $j+g+1$，则需要给前面的 $k$ 种数中的其中 $g$ 个赋值为 $j+1,j+2,\dots,j+g$，方案数为 $A_{k}^{g}$。

考虑到直接枚举 $g$ 转移时间复杂度是 $O(n^4)$ 的，可以搞一个辅助数组 $h$，每次对于一个 $j$ 先转移 $h$，$f$ 只需要从 $h$ 转移，复杂度就可以降到 $O(n^3)$。

考虑一些性质，记录 $L_x$ 表示 $x$ 首次出现在 $b$ 中的时间，若未出现则 $L_x = 0$，记录 $R_x$ 表示 $> x$ 的数第一次在 $b$ 中出现的时间，考虑 $x$ 不能出现在 $[1,L_x]$，且必须出现在 $(L_x,R_x]$。

考虑一个容斥，钦定某些 $x$ 不能出现在 $[L_x,R_x]$，此时我们只需要把每个位置能填的数的数量乘起来，就能得到答案。

考虑能否不枚举子集，一个关键的性质是，要么 $L_x = 0$，要么满足任意两个 $[L_x,R_x]$ 互相不交，于是只需要记录 $f_{j,t}$ 表示当前有 $j$ 个 $[0,R_x]$ 的区间被选中，有 $t = 0/1$ 个 $[L_x,R_x]$ 被选中，此时的带权方案数。

考虑转移，每个位置系数为其能够填的数的数量，即 $n+1-\sum_x [L_x > i]$，注意需要减去钦定的 $j+t$。接下来只需要考虑转移钦定的数量，当遇到一个 $L_x = 0$ 的 $R_x$，考虑是否加入到集合内，分别转移到 $j,t$，$j+1,t$，要注意后者系数为 $-1$。同时扫描到第二类钦定区间时，只需要同样考虑是否选即可，最后答案求和即可，时间复杂度 $O(n^2)$。

哎，还有两天 CSP 了，感觉做不动题了可能，摆一摆写写板子吧，我觉得，应该说这两个月，已经尽力了，已经相比之前，做了太多了。所以就是，没什么好说的了，就算说，期待的一切事情最后都会，破灭，那也，还是要期待，要不然或许活下去，也没有什么意义吧。所以就是，CSP rp++，希望能进 WC。

11.1~11.28

反正，CSP 爆了，也还是要训练，而且，哎反正无所谓了，既然都要训了那就，不要管别的了。

先写一下 CSP 的题解吧，感觉其实写代码的时候会有挺多 case 会挂分的。

T1，最终一定合并到某个初始存在的值上，考虑枚举，看能够有多少小于它的补过来，一定是从大到小贪心补，按照值域划分成若干个段，双指针维护能够取到的整段，暴力计算散段能取多少个即可，注意散段为空时不能计算。

T2，感觉到可以把每条线路看作点，每个车站看作边，你发现线路内部不需要时间，于是这个就很对，然后点数只有 $500$，完全图，可以直接跑 floyd，然后就做完了，应该没啥需要注意的。

T3，细节很多啊，把题解粘过来吧。

::::success[sol] 场上被自己的一些错误结论爆了，虽然心态很爆，但最后应该是会做了，想了一下出来之后写一下，好像能过民间数据，但根据细节还是不少，哎，不懂啊。

Upd 11.1，想了一下发现场上的错误结论是对的，是我证伪它的时候图是错的，并且原做法显然更简单，所以写一下吧，叫做 Sol.1，麻烦的做法叫 Sol.2。这个 1 还是挺简单的。

Sol.1

首先考虑最短路该如何求，记录 $l_i,r_i$ 分别表示每个点最远能跳到哪里，对于 $u < v$，我们可以从 $u$ 开始暴力跳 $r$，直到这个位置超过 $v$ 就结束了。同理可以从 $v$ 出发暴力跳 $l$，直到这个位置超过 $u$。

取出这两条链，首先若两条链完全相同，则最短路唯一，否则两条链只能有 $1$ 个位置不同，考虑取出这两条链，设不同的一段为 $l \to x \to r$，$l \leftarrow y \leftarrow r$，满足 $l < y < x < r$，此时我们可以分别通过 $l \to x \to r$ 和 $l \to y \to r$ 经过这个位置，产生 $2$ 种方案，而若存在多个不同位置，可以有多个断点存在多种通过方式，这样是不合法的。

于是我们说明了两条链恰好有 $1$ 个位置不同，同时你发现要求不同的两个点必须是相邻的两个点，比如上面的例子，若存在 $y < z < x$ 的 $z$，我们同样可以走 $l \to z \to r$ 这条路径，于是两条链不同的点必须是原序列上相邻的两个点。

于是就好做了，只需要枚举其中一个，就可以确定出这个断点位置，对于剩下的前后缀，我们均要求满足 $l_{r_i} = i$，分别对前后缀 dp 求出这样的合法点数量，转移只需要找到 $p = l_i$，判断 $r_p$ 是否为 $i$，后缀同理。

一些细节在于起点和终点的位置需要特判，因为最短路链走到起点和终点时会截断，也就是链只有一条边的情况，同时枚举的点可能作为起点和终点，需要算贡献。

时间复杂度也是 $O(n)$ 的。

Sol.2

应该会给出一些关键的结论，可能会写的不太清楚，现在有点说不明白话，对不起哦。考虑把点对的贡献统计到左端点上，此时有一些性质：

最短路只会往右走不会往左走。

这个结论是显然的，因为往左走会至少浪费掉一步，这样是不优的。

对于每个点 $u$，求出走 $k$ 步能走到的点，这些点应该是一段区间。

考虑记录 $R_i$ 表示每个点向右走，能到达的最远的点，首先显然有 $R$ 单调不降，我们取出一条这样的链记作 $r_0,r_1,\dots,r_k$，左端点为起点 $r_0 = u$，剩下的每一项都是上一项的 $R$，即 $r_i = R_{r_{i-1}}$。

则最短路为 $k$ 的区间应该是 $(r_{k-1},r_k]$。

最短路是 $k+1$ 的这些点，上一步应该是最短路为 $k$ 的点的一些后缀，他们的方案数应该是一段后缀的方案数之和。

只需要考虑哪些点能走到他们，你发现能到达的是一段后缀，于是满足这个条件，同时也得到一个结论是，对于同一层的点，方案数应该是随着编号单调不增的，因为他们能取到上一层的后缀越来越少。

你发现恰好 $2$ 条这个限制是很紧的，这个限制可以让我们对于每一层，只保留最右边两个点的方案数，因为若它的方案数来自于上一层 $\ge 3$ 个点的后缀，则它的方案数已经 $\ge 3$ 了，显然是不合法的。于是恰好两条只有可能是，上一层最后一个点贡献 $2$，或者上一层最后两个点分别贡献 $1$。

于是我们只需要保留三种状态：

• 这一层最右边两个点的方案数都是 $1$。
• 这一层最右边的点方案数为 $1$，倒数第二个点的方案数 $\ge 2$。
• 这一层最右边的点方案数为 $2$。

剩下的情况就是最右边的点方案数已经 $\ge 3$，显然是不合法的，所以直接扔了就行了，把上面三个东西分别记成是 ABC 三种状态的区间。

考虑怎么转移。设当前层是 $(p,r]$，下一层是 $(r,q]$，其中 $q=R_r$。我们需要求出下一层有多少个点恰好能从当前层的最后一个点转移，以及多少个点恰好能从最后两个点转移。

对于下一层的一个点 $v$，当前层最右边的点 $r$ 一定能到达它，$r-1$ 能到达它需要 $v\le R_{r-1}$，$r-2$ 能到达它需要满足 $v\le R_{r-2}$，考虑根据这个东西把后缀划分成三段。记录 $L_1=q-P,L_2=P-Q,$ 分别表示恰好有一个、两个前驱的点数。讨论三种状态对答案的贡献，以及转移到啥新的状态。

对第一种状态 A，下一层只有一个前驱的点方案数为 $1$，恰好两个前驱的点方案数为 $2$，所以贡献是 $L_2$。对 B，考虑下一层只有一个前驱的点方案数为 $1$，至少两个前驱的点方案数都 $\ge 3$，所以没有贡献。对 C，当前层所有点的方案数都至少为 $2$，下一层只有一个前驱的点方案数为 $2$，至少两个前驱的点方案数都 $\ge 4$，所以贡献是 $L_1$。

同时考虑转移到下一层的哪个状态，对于 A 和 B，如果 $L_1>0$，下一层最右边的 $L_1$ 个点方案数都是 $1$。

• 若 $L_1\ge 2$，下一层属于 A。
• 若下一层只有一个点，也属于 A。
• 否则只有最右边一个点的方案数为 $1$，倒数第二个点的方案数至少为 $2$，属于 B。

额好像有一个细节是 $L_1=0$，应该只有当前为 A 且 $L_2>0$ 时，下一层最右边的点方案数为 $2$，转移到 C。其余的情况下一层最右端已经超过 $3$ 种方案了，直接扔了就好了。

对于 C 转移更简单：如果 $L_1>0$，那么下一层还是 C，否则一定不合法，直接扔掉。这样我们已经能对一个固定起点逐层计算答案了，可以做到平方，剩下的需要一个比较容易发现的结论：

不同起点如果某一层的右端点相同，状态也相同，那么它们之后的转移和贡献完全相同。

因为你每一层的转移是只关心右端点的，而只要一个端点相同之后，后面就会走到相同的状态，我们也并不关心起点，于是相当于是同一条链上的贡献可以一起算，考虑怎么算这个东西。

场上最后半小时大概也就想到了这里，后面就写暴力开摆了，因为确实也没时间了，就还是自己太菜了。

设 $f_{r,0/1/2}$ 分别表示以 $r$ 作为某一层右端点的起点 $u$ 的数量，0/1/2 分别对应了状态 ABC。对于每个起点 $u$，第一层为 $(u,R_u]$，里面所有点的方案数都是 $1$，所以需要把 $f_{R_u,0}$ 初始化增加 $1$。

第一层没有贡献，后面每次转移时统计下一层的贡献即可。从小到大枚举 $r$，令 $q=R_r$。如果 $q=r$，说明没有下一层，跳过。否则计算 $L_1,L_2$，答案加上 $f_{r,0}L_2+f_{r,2}L_1$，然后按照前面的分类转移。

如果 $L_1>0$，当 $L_1\ge 2$ 或 $q-r=1$ 时，令 $k=0$，否则令 $k=1$。则

$$ f_{q,k}\mathrel{+}=f_{r,0}+f_{r,1} $$

$$ f_{q,2}\mathrel{+}=f_{r,2} $$

如果 $L_1=0$ 且 $L_2>0$，则只有

$$ f_{q,2}\mathrel{+}=f_{r,0} $$

其他的都是上面说的直接扔掉就行了。

由于每次有效转移都有 $q>r$，按下标递增处理就行。每个合法点对也只会在其右端点所属的那一层被统计一次，不会算重。$R$ 双指针就可以求，每个位置只有三种状态，所以时间复杂度 $O(n)$。

在大巴车上实在是要写吐了，最后那几个行间公式是 GPT 帮忙补全的，应该没有大问题，其实代码还挺短的，就是很多细节很难处理，感觉还是自己太菜了吧。

::::success[代码，过了 luogu 数据]

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int maxn = 2e6 + 10;

int n;
ll d,x[maxn];
int R[maxn],f[maxn][3];

void solve()
{
    cin >> n >> d;
    for(int i = 1;i <= n;i++) cin >> x[i];

    R[0] = 0;
    for(int i = 0;i <= n;i++) f[i][0] = f[i][1] = f[i][2] = 0;
    int j = 1;
    for(int i = 1;i <= n;i++)
    {
        j = max(j,i);
        while(j < n && x[j + 1] - x[i] <= d) j++;
        R[i] = j;
    }

    for(int i = 1;i <= n;i++) if(R[i] > i) f[R[i]][0]++;

    ll ans = 0;
    for(int r = 1;r <= n;r++)
    {
        int q = R[r];
        if(q == r) continue;

        int p = max(r,R[r - 1]),z = r;
        if(r >= 2) z = max(r,R[r - 2]);

        int la = q - p,lb = p - z;
        ans += 1ll * f[r][0] * lb;
        ans += 1ll * f[r][2] * la;
        if(la > 0)
        {
            if(la >= 2 || q - r == 1) f[q][0] += f[r][0] + f[r][1];
            else f[q][1] += f[r][0] + f[r][1];
            f[q][2] += f[r][2];
        }
        else if(lb > 0) f[q][2] += f[r][0];
    }

    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    int c,t;
    cin >> c >> t;
    while(t--) solve();
    return 0;
}

::::

T4，感觉也是有的做法简单，有的做法困难。

首先来说简单做法吧，考虑二分答案 $r$ 后如何 check，首先我们把整棵树剥掉 $r$ 层叶子，此时剩下的连通块为 $C$，若 $C$ 为空则取树的中心就可以合法，否则考虑非空情况。

考虑 $C$ 的叶子是必选的，并且已经被剥掉的点选了是不优的，因为不如放到对应 $C$ 上的叶子选。考虑对 $C$ 上的每个点求出 $h_i$ 表示挂在这个点上的子树深度。

考虑此时 $C$ 中有哪些点可以不选，由于要求 $\le 2$ 个连通块，我们能从 $C$ 中删除的只能是一条每个点度数为 $2$ 的链，若度数 $\ge 3$ 则会分成超过 $2$ 个连通块，否则这个点是叶子必须保留。

考虑找到所有极长二度链，看最多能删掉多长，只需要判断删掉的长度是否 $\ge k - |C|$。

如何求出能删掉多长，取出一条极长链，放在序列上，设为 $a_1,a_2,a_3,\dots,a_m$，考虑每个点 $a_i$ 对于保留下来的端点 $pl,pr$ 有什么限制，记录 $d_i = r - i$，则每个点要求 $pl \ge i-d_i$ 或 $pr \le i+d_i$，分别记作 $L_i,R_i$，枚举 $pl$，对于 $L_i > pl$ 的点，要求 $pr \le R_i$，于是可以维护后缀最小值求出最大合法 $pr$，判断长度是否 $\ge k - |C|$ 即可。

时间复杂度 $O(\sum len \log n) = O(n\log n)$。

以及有一个其它的做法，但我现在还只会平方。考虑枚举一条边断掉，两边需要各选出一个连通块，并且处理好各自内部的所有点。对于 $O(n^2)$ 的做法，只需要枚举一条边断掉，然后每次剥掉一层叶子，直到点数不超过 $k$，就得到了最小的 $r$。

正解大概是需要对断掉每条边快速维护这个东西？可能可以换根或者咋样。

总结。

11.2 杂题

CF2165D Path Split

为啥就想不到呢，感觉想不到的点主要在于，感觉上这个问题是可以贪心的，但并不知道从哪个角度来做。

首先可以把问题转化成最大化匹配数量，首先对于匹配若干个相同值，尽量取前面的是不劣的，考虑如果直接从前往后匹配，是否就没有办法充分利用这个性质，而我们尝试按照值从小到大匹配，发现每个点尽量全部匹配 $i+1$ 即可，可以证明这是最优的。

CF2268D AghaBalaSar and Hamed

本质简单题。

首先考虑向左只会连续跳一步，跳多步显然不优。同时除了跳到终点，不会出现向右跳之后又向左跳，因为 $j\in [i,nxt_i]$ 均满足 $a_j < a_{nxt_i}$，于是跳回去最多只能再跳到 $nxt_i$，而跳到 $[1,i]$ 显然不如最开始就跳过去。

且向左只会跳到一个更大的位置，首先把 $i>j$ 的 $dis$ 算进去，这部分全部为 $1$，然后算 $i < j$，设 $f_i$ 表示 $i$ 的答案，记录 $mx$ 表示前缀最大值的位置，则只需要分讨 $nxt_{mx}$ 和 $nxt_{nxt_i}$ 的位置，把序列分段，并从较大的一个地方转移过来。

P17337 【MX-X30-T3】宇宙分解

非常不错的一个 dp，考虑操作很简单，就是每个 1 可以向左移动或者被删掉，1 之间的相对顺序不能变。首先前缀的 1 是没法变的，于是跳过这些，只考虑后面的部分。

因为 1 可以移动到左边位置，于是从后往前考虑决策每个 0 之间放了多少个 1，维护一个 $cnt$ 表示当前后缀中 1 的数量，记录 $f_j$ 表示保留 $j$ 个 $1$ 的方案数，转移时考虑当前段内放 $k$ 个 1，则后面的段内只能放 $\le cnt-k$，这是一个前缀和的转移，可以直接做到 $O(cnt)$。

若决策完了，还需要考虑第一个 0 前面这段放多少，答案就是 $\sum\limits_{k=0}^{cnt} (cnt-k+1) \times f_k$，时间复杂度 $O(ns)$。

htoj 芦荟蓝芩

首先直觉上感觉一下这个东西，你发现每次合并两个最大的，这样是比较优的，因为你可以让最大值尽量被除更多次，那么我们考虑说明一下这件事。

首先每次只可能合并两个值，若合并了多个，我们取出其中最小的设为 $x$，假设剩余部分分别为 $A,B$，其中 $A.B$ 可以是一些合并起来了的集合，此时不难说明先合并 $A,B$，再合并 $x$ 是很优的。

于是每次合并两个值，而让最大值合并尽量多次可以减少其权重，这是很优的。于是对于一个静态的 $a$，我们的方案就是把序列从小到大排序，然后答案可以写成

$$\lfloor \frac{a_n + \sum\limits_{i=1}^n 2^{n-i} a_i}{2^n} \rfloor$$

考虑这个东西在二进制下的意义，实际上就是取出高位，留下低位，我们记录一个 $q$ 表示高位，也就是整除了多少，记录一个 $t = 2^n - r$ 表示余数，也就是当新加入一个 $> t$ 的数时会进位，记录一个 $D = 2^n$ 表示后面的每 $D$ 会进位一次。

使用线段树，对每个区间维护从右往左复合这个函数的值，相当于是加入一个 $v$，看 $v$ 复合到这个区间后的变化，合并儿子只需要先右后左即可，离散化后的值域线段树维护这个东西，加入一个数只需要修改 $O(\log n)$ 个区间。

P6880 [JOI 2020 Final] 奥运公交 / Olympic Bus

其实就是一个很早之前做过的题吧，也没有想几分钟。

很重要也很套路的想到是最短路上的边是 $O(n)$ 的，于是只有这些边需要重算最短路，其余的边只需要拼一拼就行了，于是复杂度是 $O(n^3 + m)$，前面的 $n^3$ 在于枚举一条边然后暴力更新点对。

11.3 dmy 模拟赛

感觉难度确实有提升？哎可能主要是这个 T1 做了太久，大概做了 1.5h 的样子，T2 还好，但是后面 T4 读错题了，最后 T3 T4 都没获得啥暴力，但感觉说实话这个 T2 也没啥不写的道理，然后，总之在变好就行了。

T1，做了挺久的，首先一个想法是当我们希望最小化这个值，最大值要放进来，因为一切东西和最大值平均一下，平均值都会变得更大，而比这个最大值小。

你发现实际上可以做到 $\frac{1}{k}$ 和 $\frac{k-1}{k}$，进而观察你发现最大值和最小值分别在里面必选，再发现一下，剩余选的点好像是一段前缀或者后缀，但实际上不是这样，于是考虑它实际上应当是一段区间，以最小值为例，当跳过了一个位置，我们把下一个放的换成这个是不劣的，因为变大的更少，且更容易合法，画个图感觉出来了。

于是只需要枚举区间左端点，然后二分最大合法右端点即可，时间复杂度 $O(n\log n)$，代码比较好写，但是写的时候出了问题，把 $r-l+2$ 想成了 $r-l$，大问题啊。

T2，感觉没那么难，主要就是你思考一下一个没选的点会对选了的点有什么限制，这个限制是非常非常强的，因为是非常容易产生非法条件的。

推导一下一条链的情况，你发现任意两个相邻黑点之间距离必须是相同的奇数，考虑扩展到树上，你发现奇数的性质是很好的，这使得任意一个点，最多只能两个方向的子树有点，否则这三个点中必然有两段形成了偶数路径。

枚举 d，考虑 dp 记录 $f_{u,i}$ 表示考虑了 $u$ 子树，子树内最浅的一个黑点到当前点距离为 $i$，向上继续传递，此时的方案数，考虑如何转移，你发现只需要讨论三种情况：

• 当前子树外不选，找两个子树，分别选出一个黑点，使得这两个黑点形成一对合法对，统计答案 $f_{x,k} \times f_{y,d-k-1}$，类似点分治统计贡献的方式，扫描维护前面子树和，贡献算在后面就行了。

• $u$ 选，此时子树内的点想选，必须距离 $u$ 为 $d$，也可以不选，于是系数为 $\prod (f_{v,d-1} + 1)$。

• $u$ 不选，此时找到一棵子树继承上去，有转移 $f_{u,k} \leftarrow f_{v,k-1}$，考虑找到一个当前保留的 $f$ 最大的儿子继承过来它的 $f$，整体右移 $1$ 位，剩下的暴力转移，$>d$ 的部分直接扔掉，这个复杂度感受一下每次应该是 $O(\frac{n}{d}\times d) = O(n)$ 的，枚举 $d$ 是 $O(n)$ 的。

然后就做完了，写的长剖继承过来。

T4，哦，那这个题确实很厉害，感觉我连第一步转化也没有想到，写一下这个题大致的推导过程吧。

首先考虑最简单的情况，我们记录一个 $0/1$ 序列表示一个 $[a_i \ge H]$，考虑一次操作会对这个 01 序列产生什么样的影响，你发现每次 L 操作会删除最前面一个 $1$，同理一次 R 会删除后面一个 $1$。

考虑对于单个位置，答案就是满足前缀中 1 的数量 $\ge l$，后缀中 $1$ 的数量 $\ge r$ 的最大的 $H$，这个东西实际上就是取出前缀第 $l$ 大的数和后缀第 $r$ 大的数，把 $a_i$ 与这两个数取 $\min$，于是我们会做 $a_i \le 20$ 以及 $x = y$。

考虑一个只有 L 的做法，我们差分一下，记录 $F_t(i)$ 表示 $i$ 的前缀，进行 $t$ 次 L 操作之后的区间和，则询问只需要 $F_r(i) - F_{l-1}(i)$。

考虑一次 L 操作对于前缀的影响，你发现每进行一次 L 操作，区间和就减少了当前前缀的最大值的量，于是进行 $l$ 次操作，减少量就是前缀的前 $\min(l,i)$ 大数之和，使用主席树维护前缀前 $k$ 大和，我们就可以做只有 L 的情况。

考虑加入了 R 操作，对于前缀有什么影响，我们依旧先来考虑固定一个值 $H$，维护 01 序列的问题，此时 L 操作对前缀的影响就是从前缀中删除 $l$ 个 $1$，而 R 操作会从后缀删除 $r$ 个。

若存在后缀不够删 $r$ 个的情况，此时就会从当前前缀里继续删剩下的，你发现这个总共删除的数量是并不好维护的，并不好直接算区间和，尝试避免这种情况。

考虑找到一个 $H$ 使得考虑 $H$ 的 01 序列，其中 $1$ 的数量 $\ge l+r+1$，你发现这个数不会出现不够删的情况，也就说整个序列中被删除的 $1$ 的数量一定是 $l+r$ 个，同时 $>H$ 的这些数，他们最多只有 $l+r$ 个 $1$，于是这些数最终都会被删完，不会产生贡献。

从而我们可以先把每个位置变为 $c_i = \min(H,a_i)$，接下来就可以像之前一样计算贡献，而删除的数量是确定的。

对于前缀 $i$，其新的区间和变为 $\sum c_i$，因为 L 操作而删除掉的和为区间内前 $\min(i,l)$ 的和，接下来我们只需要知道因为 R 操作删除了多少，就可以求出区间的贡献。你发现 R 操作在整个序列中总共删除了 $Hr$，我们想要求出前缀中删了多少，只需要知道后缀中删了多少，而后缀中删的和就是后缀中前 $\min(n-i,r)$ 大的和，从而我们求出了 R 对前缀的贡献。

分别维护前后缀前 $k$ 大和，以及第 $l+r+1$ 的数即可，使用主席树可以维护，时间复杂度 $O(q\log n)$。

T3，应该是比较难的题，但也不一定吧。

先考虑一个情况 $1 \to 3 \to 2$，考虑如果先合并 $3 \to 2$，则 $3$ 会被合并两次，于是只能先合并 $3 \to 1$，从而最终 $2,3$ 需要达到的数是相同的，设为 $b_i$，则结论为若 $a_u > a_v$，且 $b_u < a_v$，则 $b_u = b_v$。

考虑把 $b$ 相同的合并起来，维护他们的 $c$ 表示他们能够达到的上界，我们尝试给出一种构造，使得每个连通块都可以做到上界。

考虑按照 $c$ 从大到小构造，对于一个连通块的目标 $c$，若当前连通块内存在一个点满足其当前价值为 $c$，则直接从这个点出发，沿着一棵生成树，把整个连通块的点全部变为 $c$，剩余的边已经满足两端相等随便选就行。

否则找到连通块外一个当前 $a_u = c$ 的点，该点的 $b$ 显然只能更小，于是直接处理这条边把连通块内某个点变成 $c$，然后还是按照上面的做就行了。

说实话感觉四个题都是可能可做的题，但就是时间太少了吧，感觉做 T1 花了太久，T2 又花了很多的时间，下次其实应该在某个时间干了啥记录一下，因为确实感觉为什么，时间很快就用完了。

等会可以把代码写一下，感觉，写代码，还是大问题啊。

P10208 [JOI 2024 Final] 礼物交换 / Gift Exchange

不会做唐题，无所谓了，无所谓。

一个转化是每个点看作一个区间，首先若一些点组成的区间出现了不交的部分，则两边被划分为两个独立连通块，需要独立配对。

考虑有交的点形成了若干连续段，但连续段未必任意两个都有交，但无所谓，我们只需要让每个点送给比它更大的那个点就好了，最后会是最大的一个点送给最小的一个点。这样一定是合法的。

只需要维护一个区间内是否存在孤立点，存在孤立点的条件是，它前后最近的有交的区间都不在该区间内，记录 $pre$ 和 $nxt$，则不合法当且仅当存在点 $lst < L,nxt > R$，对 $R$ 扫描线维护 $nxt > r$ 中 $pre$ 的最小值。

考虑如何求出 $nxt$ 和 $pre$，很暴力的做法，直接开线段树，从小到大扫每个数，把他的区间赋值为 $i$，查询区间最小值就好了。

11.4

睡睡睡，困困困，做题做题哦哦哦怎么做了一两个就不会做了，摆摆摆，困困困，睡睡睡，吃饭吃饭摆摆摆做题做题回家了。

#23598. Graph Reconstruction

好难的一个题，你发现取出 $i,j,k$，并试着表示出 $a_{i,j}$，你发现这个东西应当等于 $m - d_i - d_j + e_{i,j}$，同理表示一下 $a_{k,j}$，把两者作差，惊喜的发现我们消掉了 $m$ 和 $d_j$，但这个可能并没有用？

尝试对一行的 $a$ 求和呢，你发现这个求和很有用，它应该等于 $(n-4)(m - d_i)+ d_1 - e_{i,1}$，通过枚举 $d_1$，求出每个 $S$ 对 $n-4$ 取模的结果后，你发现我们可以判断每个点是否与 $1$ 连边，判断这个 $d$ 是否合法后我们求出了 $d_1$，接下来就可以解方程还原出每个 $d$，再根据上面最开始表示的东西，我们可以用 $d$ 和 $m,a$ 表示出 $e_{i,j}$，于是最后求出了整张图。

摆摆摆，不管了，打打 CF。

CF2283

呃，写一下题解吧。

A，选择一个数之后其余数和要 $=0$，若所有数同号则为 $r-l$，否则异号，把不对称的部分删掉就好了，可以从中选一个，所以应当是 $|l+r| - 1$。

B，你发现对于两个 $i,j$，形成的周期一定是 $\text{lcm}$，而如果 $i$ 能够整除 $j$，此时 $i$ 可以作为一个周期，由于要求周期内只能有一个数，于是只有当选出集合所有数能被最小的整除才合法。

C，首先你要认真读题看到序列是 $1,2,\dots,n$，那么他们的或应当是 $2^{h+1} - 1$，$\times 2$ 相当于左移了一位变成了 $2^{h+2} - 2$，我们只需要构造到 $2^{h+2} - 1$ 即可，首先能用到的只有 $1,2,4,8,\dots$ 这些数，因为这些是每一位里最小的，影响也是最少的。那么就从大到小考虑每一位，如果这一位当前是 $0$ 就 $\times 2$，此时只会对更低位产生影响，然后就构造出来了。

D，首先你发现不对劲啊，既然已经变成黑的不会变，那黑点数量是确定的啊，偶数就是 $n$，奇数是 $n-1$，从而只有三种情况，分别是 $1,n,\frac{n+1}{2}$ 这三个位置是灰色，判断一下某种方案是否能做到灰色为 $1$ 即可，而这个也是好做的，你要找点对是否跨过这个点，直接以这个点为根给每个连通块染色就好了。

E，怎么不保证 $\sum n$ 啊，没有人类了。

首先一个容易的观察是，你发现如果要用到第二个限制，那这个集合必须是 $01$ 同时出现，且只能是 10，01，101，010 其中的一种，考虑这个贡献，这样的位置贡献为 $2$，而其它的贡献为 $1$，答案可以看作 $n + $ 用这样区间覆盖最多的位置数。

这个最多的位置数是可以直接 dp 求出来的，设为 $g$，考虑如何算方案数，一个暴力 dp 是记录下当前有多少多余的 $0$，此时 $1$ 是能算出来的，但这个还是记多了，其实除了极长的 01 交替段，剩下的部分是必然作为第一类被选中的，我们只需要求出，$x$ 个数划分为若干个集合的方案数，这个可以斯特林数预处理一下然后求和，然后你再处理一下每种长度的 $01$ 交替串的系数就好了。

F，考虑什么样的边是不必要的，你发现如果 $i\to j$，能找到一个 $k$ 使得 $i$ 连向了 $k$，且 $k\le r_i$ 即可，因为 $i\to j$ 已经保证了 $i \ge l_j$，而由于边都是从小到大，一定有 $k > l$。

问题变为找有多少必须选的边，也就是找到它的 $nxt$ 表示连出去的最小的编号，若 $j \in [l_i,r_i],nxt_j > r_i$ 则这个 $j\to i$ 是必选的，否则一定可以替换。

于是只需要求这个东西，从小到大加入每个点，并处理 $r_i = x$ 的这些区间，看他们区间内是否有点的 $nxt > x$，只需要加入一个点时把他的区间赋值为 $0$，初始为 $1$，然后查询区间和就好了。

G，还不会，明天再看吧，还有模拟赛，睡觉了。

11.5 dmy 模拟赛

T1，首先考虑如何最小化这个 $d$，若存在 $cnt_x \ge \lceil \frac{n}{2}\rceil$，则答案为 $2\times cnt_x - n$，因为无论你咋走选到的颜色都会是 $x$，而尽可能多的抵消就可以得到这个结果。

否则答案为 $n\bmod 2$，考虑如何做到，我们首先考虑这样一件事：找到两个相邻的位置 $x，y$，你发现这两个的操作序列应当是分别为 $x,A$ 和 $A,x$，其中 $A$ 表示一种操作序列。

于是对于序列的任意一个位置，要么他们的 $d$ 相差 $1$，要么某个 $d = 0$，于是若相邻两点的最终 $d$ 均 $\ge 2$，则他们最终的 $col$ 均相同。

于是同样有结论若两个相邻位置最终的 $col$ 不同，则他们的 $d$ 必然不都 $\ge2$，于是我们可以取到一个 $d < 2$，同时又 $d$ 同余 $n$，于是可以取到答案。

于是先从 $1$ 出发模拟一遍，然后从 $k$ 满足 $k$ 的终点颜色与 $1$ 的终点颜色不同，找到这个 $k$，我们就找到了两个最终颜色不同的位置，接下来把 $1$ 的颜色看作基准颜色，则只要在保证恰好有一个基准颜色的前提下，把两个位置移动到相邻，即可取到答案。

不妨维护为 $l,r$，每次取出 $mid$，若 $mid$ 的终点为基准颜色，则把基准颜色的那个端点修改为 $mid$，否则把另一个端点修改，这样就可以找到相邻的颜色不同的位置。

时间复杂度 $O(n\log n)$。

T2，首先考虑一个暴力，考虑每个区间内的次小值，按照这个从小到大做，每次判断如果这个区间需要操作则更新操作，并更新其它区间的次小值，使用堆维护可以做到 $O(nm\log n)$。

考虑直接从小到大扫描高度 $h$，考虑一个区间内 $> h$ 的点的数量，若数量为 $1$ 则当前只剩下最大值，必须修改，若数量为 $\ge 2$ 则可以后面再修改，若只有 $0$ 个同样不需要管。

考虑如何维护这个东西，你发现删除一个点之后，其实只需要关心它左右相邻的点就好了，因为限制是只剩一个，所以只需要考虑相邻的就可以判定存在性。而判定实际上是一个二维数点问题，设当前点为 $p$，前驱为 $L$，后继为 $R$，则一个点是区间内最后一个，当且仅当 $l_i \in [L,p],r_i \in [p,R]$，使用主席树维护即可。

T3，感觉属于是，根本做不明白题，考察选手细节和分析性质能力。考虑这样一个做法，首先你把合并序列写出来，应该是一个长度为 $2n-2$ 的序列，分别由 $n$ 个 $a$ 序列中的数和 $n-2$ 个 $b$ 中合并出来的数组成，你发现我们希望最小化的是 $a$，这个操作序列相当于是 $a$ 合并上一个 $b$ 序列，而两个序列合并上同一个序列是不会改变字典序大小的，于是我们希望最小化 $S$ 序列（合并序列）。

分析一下这个 $S$ 具有哪些性质，设每次合并的点对分别为 $x_i,y_i$，则序列 $S$ 就是 $x_1,y_1,x_2,y_2\dots,x_{n-1},y_{n-1}$。首先有整个序列单调，同时 $x_i + y_i = b_i$，于是我们可以只考虑序列 $x_i$，而序列 $y$ 是随之确定的。

接下来感觉也太 adhoc 了，根本不是人类能想出来的吧。

我们把所有的 $b$ 称为已确定的值，这些值是必须出现在 $S$ 中的，我们先考虑不存在某个已确定的值 $v$ 满足 $2v = b_i$ 的情况。

你发现此时如果 $2v < b_i$，则 $S_{2i-1},S_{2i}$ 不能都 $\le v$，同理若 $2v > b_i$，则不能均 $\le v$，从而 $v$ 能填的位置实际上只有两个，也就是 $y_i$ 和 $x_{i+1}$ 其中之一。

考虑现在把这些 $b$ 插入到刚刚我们求出的这些应该在的间隔里，首先若某个间隔内放了 $> 2$ 个，则直接不合法，若放了恰好 $2$ 个 $a\le b$ 则按顺序放进去即可，若放了 $1$ 个，则无论放左边还是右边，实际上都有 $x_{i} \le b_i - v$，$x_{i+1} \ge v$。

现在考虑加入了一些 $2v = b_i$ 的 $v$，你发现这些 $v$ 的形态应当是，在中间形成了若干个连续段，且只能在两端点分别填 $v$。

从而在删除掉 $2v = b_i$ 的这些点后，整个序列依旧是一条链，链上有一些限制，形如 $x_i + x_{i+1} \ge S_i$，$x_i,x_{i+1}$ 中需要有一个位置填了，且左右分别有下界。

考虑倒序 dp 求出每个位置的下界，然后正着贪心，在符合限制的前提下，取到下界即可。

时间复杂度为 $O(n\log n)$，$\log$ 是二分找到每个 $v$ 填的位置 $i$。

T4，感觉其实可能是比 T3 简单的题？

首先考虑一个 $O(n^2\log n)$ 的一个做法，首先你需要有一些观察：

给每个点赋值一个 $h_i$，若对于每个点均满足 $s_i = h_i \bmod 2$，且对于每个 $u,h_u \ne 0$ 其连接的所有边中存在一个点 $v$ 满足 $h_u = h_v + 1$，则该方案是合法的，而最长的一条链即为全局 $h$ 的最大值。

这个条件实际上是充要的，考虑如何给出一组合法的构造，只需要对于每条边，从 $h$ 较大的端点指向 $h$ 较小的端点即可。

于是可以给出一个 dp 的判定，设 $f_{u,i,0/1}$ 表示 $u$ 的子树，$h_u$ 填了 $i$，$u$ 是否需要父亲来提供一个 $h_u - 1$，是否可行，直接二分最大值 $H$，dp 数组存 bool 可以做到 $O(n^2\log n)$，如果想做到平方可以把 dp 数组记录子树内 $\max$，然后转移取 $\min$，前后缀优化可能可以做到平方。

11.6 杂题，构造

做了一下验题模拟赛，感觉还行啊，题都还不错，风格不太一样，T4 还没做。

T1，看到这样的限制不难想到建图，考虑建图后对于每个连通块确定一个根，先假设它的值为 $0$，则可以求出连通块内每个数与它的相对异或值，若存在矛盾的则直接不合法，否则对于每一位确定 $0/1$，只需要取 $\min$ 即可。

T2，考虑到 $k \le 2000$，同时你发现对于一个 $S$，选 $S$ 的子集产生的贡献一定 $\le$ 选 $S$ 产生的贡献，于是考虑先把全集扔进去，然后每次取出堆内贡献最大的，设取出的是 $x$，则把 $x$ 去掉每一位之后的状态加进堆，只会加 $K$ 次，使用 bitset 可以维护每个状态的贡献。

T3，首先这个数据范围看上去就是一个指数很大的 poly 的复杂度，考虑首先可以把这个排列看作是位置与值的匹配，则我们可以把一个排列的贡献拆到每一条分界线上，每一条分界线的贡献应当是跨过这条分界线的匹配数量。

从而我们可以设计一个 dp，考虑设 $f_{i,j,k,l}$ 表示考虑了前 $i$ 个位置，当前有 $j$ 个值和 $k$ 个位置还尚未匹配，需要跨过这条分界线，此时贡献和为 $l$ 的方案数，考虑记录 $j,k$ 实际上是不必要的，只需要记录其中一个，设前面一共有 $ca,cb$，则满足 $j - ca = k - cb$，于是状态数是 $n^2d = n^4$ 的。

考虑你已经能求出来第一问，现在要最小化字典序，从前往后依次枚举每个位置填什么，并计算这样填之后后面的方案数，若方案数 $< s$ 则直接把 $s$ 减去方案数并且增大这个位置填的数，否则确定了这个位置填什么往后坐就行了，时间复杂度 $O(n^6)$。

T4，首先你发现，对于一个点双，你可以把割点取出来，点双里剩余的其它点，直接建一个虚点连到保留出来的割点上，于是问题转化到了树上。

考虑设 $f_{i,j}$ 表示第 $i$ 轮后停在 $j$ 的最小代价，你发现转移实际上是取出全局 $M = \min f_i$，把每个位置更新成 $\min(f_i,a_i + M)$，然后做子树加。

考虑这东西没那么好维护，但是你要求的是 $\min$，于是你可以把贡献拆开到 $f$ 的变化以及 $a_i + M$，两部分取 $\min$ 即可，然后线段树分开维护就行了，时间复杂度 $O(n+m+q\log n)$。

11.7~11.9 模拟赛，杂题

还以为时间错乱了，原来是看错日期了，差点以为自己中间怎么啥也没干摆了一天。

T1，考虑相邻两个点之间的关系实际上是差分约束的关系，于是考虑建图之后做一遍 dij 就好了，注意开根号，开根号可以先粗略开一下，然后上下浮动 eps 这样子开。

T2，感觉主要需要想到的东西在于，如何处理这个长度 $\ge d$ 的限制，其实这个是非常套路的东西啊，定义一个 $b_i$ 存储 $i$ 向后 $d$ 的信息。然后限制变为求连续段数不超过 $d$ 的区间数量，这个显然是可以双指针的，且新序列每个区间对应了原序列一个区间，只需要维护对每个高度连续段数的最大值，双指针一下就做完了。

T3，是一个非常牛的题啊！

首先先来看一下相交数量为奇数的弦具有哪些性质，考虑把叶子从左向右按照奇偶进行黑白染色，则你发现同色节点形成的弦是会被点亮的。

考虑每个叶子的颜色可能是什么情况，我们考虑对叶子之间进行配对，对于 $u$ 的子树，若其中有偶数个叶子，我们直接将他们两两配对，表示他们之间必须异色，而如果有奇数个，我们保留其中一个，一直向上传递，直到出现了另一个奇数节点，就与它配对。

这样实际上刻画了叶子之间的染色关系，此时把这些关系称为 $A$ 类边，原图给出的配对关系称为 $B$ 类边，则形成了若干个环，且每个环上恰好 $t$ 条 $A$ 和 $t$ 条 $B$，你发现 $A$ 边端点都是异色的，而 $B$ 边若同色则会产生一条点亮的弦，若异色则不会。

同时由于走一圈会回到同一个点，于是若选择了 $x$ 条边同色，则有 $2t - x$ 异色，我们要求它是偶数，也就是每个环选出的同色边应当是偶数，从而 $k$ 也应当是偶数。

然后问题就很简单了，每个环选出偶数条边，显然从小到大两两配对，然后全局取最小的 $\frac{k}{2}$ 对，于是就做完了。

T4，你首先发现跳一次实际上是跳到 $lca(u,v),lca(u,x),lca(v,x)$ 三个点中深度最大的那一个上，考虑连续跳实际上是可以合并的，你发现如果经过两条相交的链，则等价于跳到他们相交的部分这条链上，否则他们不交，找到两条链的最短路，假设是从 $x \to y$，则连续跳这两条链等价于跳到 $y$ 这个点。

使用线段树维护连续跳 $[l,r]$ 这些链等价于跳到哪条链，最后从 $x$ 跳一次，做最开始那个跳 lca 的操作就行了。

CF2279

A，考虑一次修改操作如果有用，是一定要把全局 $d$ 的最大值减小的，而你发现修改一个区间，只有端点处会产生一些变化，中间的部分实际上是进行了 $\times 2$，于是可以确定一个端点一定在取到全局最大值的位置上，然后枚举另一个位置算贡献就行了。

B，怎么是 $998$ 题，看上去很困难，实际上你发现，对于一个选出的集合，最大值和次大值必然是不稳定的，而其余的部分要求必须稳定，于是记录 $f_{i,S,c}$ 表示从大到小考虑到 $i$，此时 $i+1,i+2,i+3$ 的状态是 $S$，集合中已经有了 $\min(2,c)$ 个数，此时的方案数。

记录 $c$ 这一维主要是为了避免限制最大和次大值，然后转移就行了，最后统计答案就是所有 $c = 1/2$ 的合法状态。

C，感觉比 B 简单啊，首先这个显然只需要关系最大值和次大值，你发现次大值只能是 $\sqrt l$ 级别的，于是直接枚举次大值就做完了，要注意有一些边界的细节。

D，首先你需要读懂题，大概意思是两个人，第二个人可以任意走，若有连边则两人可以交换位置，求最小操作次数从 $w,x$ 分别走到 $y,z$。

由于交换位置要求必须相邻，假设 $w$ 路径上经过了 $p_1,p_2,\dots,p_k$，则第二个人应该每次先移动到 $p_{i}$，此时第一个人位于 $p_{i-1}$，然后进行交换，第二个人再从 $p_{i-1}$ 走到 $p_{i+1}$。

于是把第一步和最后一步看作点权，中间是一条最短路，对于一条最短路上每个点，会进行两次移动和一次交换，贡献为 $3$，而对于起点和终点，实际上是找他们的邻域中两个点，然后把第二个人分别从 $x,z$ 移动到这两个点。

注意一下不需要走中间的贡献。

CF1580B Mathematics Curriculum

首先考虑子集最大值集合长什么样，对于一个 $p$ 它对应的集合应当是 $[1,p]$ 的后缀最大值和 $[p,n]$ 的前缀最大值。从 $n$ 所在的位置考虑，两部分独立计算并 $+!$，实际上就是一棵大根笛卡尔树的结构，而集合大小为 $k$ 的相当于大根笛卡尔树第 $k$ 层的点，于是问题变为求有多少排列，其大根笛卡尔树的第 $m$ 层点数为 $k$。

考虑这样一个 dp，记录 $f_{i,j,k}$ 表示考虑了 $[1,i]$，当前的笛卡尔树第 $j$ 层有 $k$ 个点的方案数，则最终答案为 $f_{n,m,k}$。

考虑如何转移，首先当前第 $d$ 层在左右子树分别应当位于第 $d-1$ 层，考虑左右子树分别有多少点，设左边有 $l$，右边应当有 $s-1-l$，枚举左右 $d-1$ 层分别有多少点，则有转移 $f_{l,d-1,x} \times f_{r,d-1,y} \to f_{l+r+1,d,x+y}$，由于两端独立，我们需要分配值域，于是系数为组合数 ${s-1} \choose l$，时间复杂度为 $O(n^2mk^2)$。

不是啊，$n=100$ 过 $n^5$ 的来了，但应该需要大力剪枝，没招了。

P10283 [USACO24OPEN] Identity Theft P

简单题。

考虑把每个串结尾看作黑点，题意要求每个黑点子树内没有点，考虑建出 01 trie，对于一个不合法的黑点考虑它能移动到的位置，你发现有两种方式，一种是找到子树内一个完全没有出现过的分支，移动过去；另一种则是找到子树内一个黑点 $u$，由于这个黑点的左右子树一定都没有黑点，于是把当前点和 $u$ 分别放到左右儿子即可。

使用堆维护这两种可以放的位置，每次填进代价最小的集合，做启发式合并即可。

CF1830D Mex Tree

树是一个二分图。

首先考虑进行一些转化，假设所有点对贡献均为 $2$，然后考虑哪些点对贡献不是 $2$，我们希望最小化减少的贡献，你发现只能是一条路径全是 $1$ 或者全是 $0$，于是只保留两端全 $0$ 和全 $1$ 的边，形成了若干连通块，每个连通块贡献为 $siz(siz + 1)$，$0$ 连通块贡献只有一半。

于是有一个 dp 是设 $f_{i,j,0/1}$ 表示考虑了 $i$ 子树，$i$ 所在连通块大小为 $j$，颜色为 $0/1$，此时的最小代价。

转移只需要考虑这条边两端颜色是否相同，不同显然从 $v$ 最小的一个状态加过来即可，若相同，对于两个大小分别为 $x,y$ 的块其额外产生 $2xy$ 的贡献，注意 $0$ 连通块贡献仍然是一半。

这样做的复杂度是 $O(n^2)$ 的，考虑第二维状态并不会太大，考虑对树二分图染色，此时能产生的代价是 $\frac{3}{2} n$，于是比这个还大的一定全都不优，你发现 $j^2 \le \frac{3}{2}n$，此时的 $j$ 只有 $O(\sqrt n)$ 的级别。

感觉主要在于要想到，把路径这种不好计数算贡献的问题，转化为连通块这样好算贡献的东西，然后就好做了。

#23592. Average of Averages

首先你需要看到 $a_i = i$，那么就不难计算出对于每个区间它对的答案是什么，你发现就是 $\frac{l + r}{2}$，也就说我们要统计有多少个区间在线段树上的权值等于原序列权值，对于线段树每一层，处理跨过 $mid$ 的区间，考虑这个区间的贡献可以拆成 $\frac{lst_l + pre_r}{2}$，其中 $lst$ 表示询问 $l,mid$，而 $pre$ 表示询问 $mid + 1,r$，于是区间合法等价于 $l+r = pre_r + lst_l$，把相同的放一边就可以得到 $pre_r - r = l - lst_l$，于是对于线段树每个区间维护所有后缀和前缀的询问值，然后开桶查询即可。

每个端点只会在 $O(\log)$ 层分别作为一个前缀和后缀的起点，因此时间复杂度 $O(n\log n)$，但这个东西有巨大的常数，你发现长度相同的两个线段树节点其答案应当是完全相同的，于是我们事实上用不到那么多 stl，以及对于多次询问相同的 $n$ 记忆化一下就行了。

#637. 【美团杯2021】A. 数据结构

考虑一个数在什么情况下会没有贡献，你发现要求 $x$ 的这些位置都要被 $+1$ 并且 $x-1$ 这些位置全都不被 $+1$，先考虑第一个限制，找到 $x$ 所在位置的 $\min$ 和 $\max$，要求区间必须包含这些位置，然后找到任意两个相邻的 $x-1$，区间只能位于这些点内部，于是问题变为了若干个矩形，每个矩形具有贡献，每次询问单点处贡献和，线段树扫描线可以简单维护。

ICPC 成都

看了一下成都站的题，感觉好像还不错，哎感觉 ICPC 和 CF，其实跟 OI 题的风格还是不那么一样吧，但总之也有一些不错的题，大致按照难度开始些。

D，考虑 B 死之前，两个人受到的伤害可以表示成 $S \times a,S \times b$，且这个 $S$ 可以任意取到，只需要满足 $S < \lceil \frac{y}{a} \rceil$，考虑最后一下攻击，最劣情况下两个人都进愤怒，$S$ 会增加 $4$，于是要求第一个人的血量 $> (S_{\max} + 4) b$ 即可。

M，首先如果我们确定了哪些点将会作为分界点，那么这些点取的尽量大是不劣的，所以首先取 $a_1 = r_1$，接下来往后找到第一个满足 $l_i > r_1$，则在该位置及之前必然产生了分界点，也就是存在某个位置，选取了 $>r_1$ 的位置，而我们希望这个位置选的数尽可能大，于是找到 $r$ 最大的选上即可，然后继续做后面的区间即可，我们每次选出的分界点都是必要的，且取到了最优方案，于是就是对的。

K，考虑二分答案转化为判定性问题，问题转化为每个 $b_i$ 可以放在 $[a_i-d,a_i+d]$，判断是否存在合法方案使得相邻的两个点距离 $\ge l_i$，最开始的想法是 $b$ 单调从前往后贪心，但你发现转成判定性问题后这个贪心策略并不成立，因为我们不再要求最优化，于是考虑维护一下当前点能够放的区间，每次与 $l_i,r_i$ 取交后就是当前位置能放的区间，若存在某个位置为空集则不合法，否则合法。

C，首先考虑一个朴素的 dp，设 $f_{i,j,k}$ 表示考虑前 $i$ 个位置，满足 $a_0 = 0,a_i - a_{i-1} \in [0,1]$，此时 $a_i = j$，前缀和为 $k$ 的方案数。

时间复杂度 $O(n^4)$，多测无法通过，但这个 $n$ 只开了 $100$，感觉上就是一个 $O(n^4)$ 预处理然后询问的东西，考虑能够复用什么东西。

你发现对于每条限制，它前面的前缀和实际上是钦定好的，两个限制分别为 $(u,x),(v,y)$，不妨设一个 $b$ 数组记录 $a_i - x$，你发现这样 $u,v$ 之间这一段又变成了一个从 $0$ 开始的问题，可以使用前面的 dp 数组直接找方案数。

那么首先这一段的区间和你是知道的，只需要枚举一下上一组最后一个数是什么，即可进行转移。假设相邻两个限制为 $(p,u),(q,v)$，令 $d = q - p$。

设 $g_x$ 表示考虑前面这些限制，当前最后一个数是 $x$ 的方案数，枚举上一个末尾为 $y$，则有转移 $h_x \leftarrow g_y \times f_{d,y-x,u-v-dx}$，不难做到 $O(n^2)$ 处理每次询问，总时间复杂度 $O(n^4 + Tn^2)$。

I，考虑对整个森林做 dfs，一个点入队时的时间戳记作它的 $a_i$，离开时时间戳记作 $out_i$，此时这 $2n$ 个数恰好被分配给了所有的数。考虑说还原时只需要根据这个序列就行了，依次枚举时间 $t= 1,2,3,4,\dots,2n$，如果当前时间戳存在某个 $a_i$，则把这个点与栈顶连边，并把这个点加入栈，否则弹出栈顶元素即可。

时间复杂度 $O(n)$。

H，考虑维护一个队列，若队列为空直接加入，否则询问这个数与队尾的关系，若这个数 $\ge$ 队尾则放在队尾，否则放在队首。不难发现通过这个操作我们把所有全局最大值挪到了队尾的连续一段，从末尾去掉一个，从前往后再做一遍，总操作数为 $n+1 + n + 2 = 2n - 3$ 次。

A，首先你需要看到 $a_i = i$，那么就不难计算出对于每个区间它对的答案是什么，你发现就是 $\frac{l + r}{2}$，也就说我们要统计有多少个区间在线段树上的权值等于原序列权值，对于线段树每一层，处理跨过 $mid$ 的区间，考虑这个区间的贡献可以拆成 $\frac{lst_l + pre_r}{2}$，其中 $lst$ 表示询问 $l,mid$，而 $pre$ 表示询问 $mid + 1,r$，于是区间合法等价于 $l+r = pre_r + lst_l$，把相同的放一边就可以得到 $pre_r - r = l - lst_l$，于是对于线段树每个区间维护所有后缀和前缀的询问值，然后开桶查询即可。

每个端点只会在 $O(\log)$ 层分别作为一个前缀和后缀的起点，因此时间复杂度 $O(n\log n)$，但这个东西有巨大的常数，你发现长度相同的两个线段树节点其答案应当是完全相同的，于是我们事实上用不到那么多 stl，以及对于多次询问相同的 $n$ 记忆化一下就行了。

G，好难的一个题，你发现取出 $i,j,k$，并试着表示出 $a_{i,j}$，你发现这个东西应当等于 $m - d_i - d_j + e_{i,j}$，同理表示一下 $a_{k,j}$，把两者作差，惊喜的发现我们消掉了 $m$ 和 $d_j$，但这个可能并没有用？

尝试对一行的 $a$ 求和呢，你发现这个求和很有用，它应该等于 $(n-4)(m - d_i)+ d_1 - e_{i,1}$，通过枚举 $d_1$，求出每个 $S$ 对 $n-4$ 取模的结果后，你发现我们可以判断每个点是否与 $1$ 连边，判断这个 $d$ 是否合法后我们求出了 $d_1$，接下来就可以解方程还原出每个 $d$，再根据上面最开始表示的东西，我们可以用 $d$ 和 $m,a$ 表示出 $e_{i,j}$，于是最后求出了整张图。

CF1083D The Fair Nut's getting crazy

zazhemenan。

吐了，感觉他妈的，啥简单题也自己做不出来。

感觉不会做的点就在于，没有考虑枚举交集然后算贡献？其实只要想到枚举交集，然后把贡献写出来，这东西可以直接扫描线维护，然后就做完了。

这就是 3500 吗（。

P14706 [ICPC 2023 Tehran R] Cup of Tea

感觉是随到了一个好题啊。

来一个 $O(n\log^2 n)$ 的做法。

首先你可以考虑一个暴力建图的做法，你发现一定是从某个补给点开始走，每次走不超过 $k$ 的距离，于是你尝试把每个点向周围不超过 $k$ 的点连边。

考虑如何建这些边，考虑树上距离不超过 $k$ 的点，能否进行点分治。对于当前分治中心，求出每个点到分治中心距离 $d_i$，则对于一个 $u$ 能到的 $v$ 是一段前缀，可以考虑前缀优化建图，而不难发现对于位于同一子连通块内的点，这样连边显然是不优的，于是不需要管去重的问题。

前缀优化见图后总边数为 $O(n\log n)$ 级，直接从 $1$ 出发做单源最短路，时间复杂度 $O(n\log^2 n)$。

还有一个更优秀的做法，你发现比较优的路径中，到达 $u$ 的补给点只能是它的某个祖先或者最近的一个儿子，于是预处理出子树内最近的一个补给点，考虑 dp，记录 $f_{u}$ 表示从 $1$ 出发，进入到 $u$ 子树内的一个补给点再回到 $u$ 所需要的最短路，考虑转移的限制是值域维上的一段后缀，使用树状数组维护当前最优转移，可以做到 $O(n\log n)$，树状数组需要支持撤销操作。

11.10 dmy 模拟赛

睡了一小时，好困啊。。。

T1，考虑两个序列先正常操作一段前缀后，删掉 A 序列中间一段，我们希望对于每个 $l$ 求出最小的 $r$ 使得删除区间 $l,r$ 之后 A 的后缀能被当前 B 的后缀消除掉。

记录一个 $f_i$ 表示想要赢 A 序列的 $[i,n]$ 后缀，需要从 B 的哪个位置开始消，你发现这些位置构成了一个前缀，于是只需要维护最大值，同时你发现对于每个 $i$ 对应的 $f$ 是单调的，于是可以双指针求双指针维护答案，时间复杂度 $O(n)$。

T2，首先有一个想法是如果没有这个 $T$ 会怎么做，你发现只需要分别找出黑白点的带权重心，就可以做这个问题，于是有一个想法是，加上 $T$ 之后这个带权重心是不是只会往中间移动，但你发现这个 $T$ 很大实际上这个做法并不太好找到贡献变化的点，还是需要分析贡献。

考虑把贡献拆到每条边上来，你发现每条边的贡献实际上可以看作两部分，第一部分是一些点要到达集合点必须要经过这条边，记录 $l_1,r_1,l_2,r_2$ 分别表示两种颜色的点，位于该边左右的点数，考虑集合点尽量放在多的那一侧，让尽可能少的点跨过这条边，此时贡献为 $\min(l_1 + r_1) + \min(l_2 + r_2)$。

但你发现我们前面贡献中，取到最优的两个集合点位于这条边两侧，此时就需要决策，如果最终方案中它们位于这条边两侧，则贡献为 $t$，否则我们要把其中一个移动到另一边，贡献为 $\min(|l_1 - r_1|,|l_2 - r_2|)$，于是最小的贡献就是这三个东西取 $\min$。

我们希望尽量取到这个结果，于是接下来我们尝试说明可以做到这件事。你发现伴随着 $t$ 的增加，取到这个 $t$ 作为 $\min$ 的只会越来越向内锁，并且对于前缀和后缀分别都能取到刚刚的那个 $\min$，于是你可以做到这件事情，于是只需要每次询问维护子树大小就行了，时间复杂度 $O(nq)$。

T3，唉，不想写了。

大概就是你贪心做，对于一个区间找到最小的满足 $a_i > \oplus_{j=i+1}^r a_j$，那么谁到这个地方谁就赢了，可以算出每个点的答案。

你发现可以从后向前维护这个过程，维护当前区间获胜需要次数，若 $a_i$ 是符合上面条件的点，则直接 $f = 0$，否则若这个位置为 $1$，则没有任何选择方案，必然是 $1$ 次操作，转移到 $f+1$，否则 $a_i \ge 2$，此时若后一个状态先手必败，则我们一次拿完，对手必败，否则我们留一个，到下个状态我们是先手。

你发现先手必胜和必败只取决于奇偶性，于是直接根据后面奇偶性决定 $+1,+2$。使用线段树同样可以维护这个东西，但扫描的过程中可能涉及到许多次的单点修。

你发现一个点合法实际上是对于前缀异或和的限制，于是我们按照值域来扫前缀异或和，每个点状态为合法的时候应当是 $O(\log n)$ 段区间，于是单点修该次数 $O(n\log n)$，总复杂度 $O(N\log V\log n)$。

11.11 树上问题

看了一下前面的记录，其实还是有很多题，感觉做的太草率了，没有学到该学到的东西吧。

AT_agc024_d [AGC024D] Isomorphism Freak

做出来了，哦哦的耶。

首先你尝试构造这个最小的颜色数量，你发现连续的三个点是没有办法两两同构的，同时同构的树应当要求他们的直径中心的点集映射过来之后是相同的。

于是感觉上，最优的颜色数量应当是从直径的中心出发，让每层的所有点同构，而我们也不难算出总的叶子数量，由于我们要让每层同构，于是每层的每个点的儿子数量应该是这一层所有点儿子数量的 $\max$，记作 $b_i$，则最终儿子数量应该是 $\prod\limits_{i=0}^h b_i$，但这个可对于中心数量为 $1$ 或者 $2$ 会产生一些小的差异，但这都是小问题。

注意当只有一个中心时，我们可能通过取它邻域中某个点，使得这两个点作为中心，并在一端补上一些叶子，这种情况未必是不优的，但直接暴力做一次才 $O(n)$，你直接对所有点做这个也才是 $O(n^2)$ 的，只开了 $100$，显然显然显然能过。

AT_agc018_d [AGC018D] Tree and Hamilton Path

这个题，很厉害啊，感觉就是一个见过就很牛的题。

考虑我们第一想法一定是让每条边尽可能多的被访问到，于是考虑能不能先求出每条边的上界，设这条边左右的点数分别为 $l,r$，则有上界 $2 \times \min(l,r) - [l = r]$，考虑想要取到上界就需要尽量每次让子树内匹配到子树外。

而你发现只要我们找到重心，并每次从一个子连通块连到另外的子连通块，就一定能取到这个上界，因为重心的性质天然满足了任意子树大小不超过 $\frac{n}{2}$，于是必然能够每个点向子树外完成匹配。

但你发现我们要求的是哈密顿路径，这使得第一次被取到的这个点，它到重心的路径上会少了进来匹配的那一段，也就说最终的贡献实际上是每个边取到上界的价值和，减去从重心为端点的一条路径，你发现这实际上就是找到一条重心连着的一条边。

#943. Dynamic Diameter

修一条边权，维护树的直径，强制在线。

考虑求出欧拉序，也就是每个点每被到达一次就记录一次 tag，则总共会有 $2n-1$ 个位置，考虑在每个位置维护节点的深度，则对于任意 $u,v$ 作为端点的路径，可以表示为 $dep_u + dep_v - 2 \times dep_{lca}$，考虑如何维护 $dep_{lca}$，你发现在欧拉序上，这相当于是对区间取 $\min$，于是只需要维护一棵线段树，维护区间内有序三元组 $u < v < w$ 对应的 $a_u + a_w - 2\times a_v$ 最大值，线段树不难维护。

修改时相当于对子树内深度全部修改一个增量，直接支持区间加即可，线段树维护区间 $\min,\max,u < v,-2a_u + a_v$ 以及 $u

CF2182G Short Garland

哎，当你感觉一个题完全没有任何可做的空间的时候，其实就应该重新读题一下。

考虑题目的摆放方式，实际上是按照当前树的一个 dfs 序去做，也就是说我们一定会进入一棵子树走到叶子再进入下一个子树。

加入当前处理 $u$，你发现从一个叶子出发，下一个放在其它子树，这中间需要花费的距离是一样的，均为 $dep_x - dep_u + 2$，于是一个叶子能到达下一个子树当且仅当 $dep_x \le dep_u + k - 2$。

考虑记录 $f_{u,d}$ 表示考虑了 $u$ 的子树，处理完其子树且位于一个深度为 $d$ 的点，此时的方案数。考虑如何转移，记录 $g_v$ 表示 $\sum\limits_{d \le dep_u + k} f_{v,d}$，则你发现转移实际上是 $f_{u,d} \leftarrow (m-1)! \sum\limits_{v \in son_u} f_{v,d} \prod\limits_{w \ne v} g_x$，暴力转移时间复杂度 $O(n^2)$。

考虑这个 $\prod$ 可以记作是 $h_v$ 然后前后缀积预处理出来，于是每次转移相当于是把 $f_v$ 全局乘上一个东西，然后转移到 $f_u$，然后再把 $f_u$ 乘上一个东西。

考虑线段树合并，维护区间和、区间乘一个数，时间复杂度 $O(n\log n)$。

11.12 dmy 模拟赛

T1，感觉很简单啊，但大家好像都觉得很难。感觉就是，你注意到只需要相邻两个符合限制，并且你发现相邻两个只关心最后一次排序到他们，然后就做完了，从后往前按时间维枚举选的集合就行了，感觉还是说明之前见到的 trick 有点用的。

T2，记录 $q$ 为 $[$ 的逆排列，你发现一次操作不会改变 $q$ 的大根和小根笛卡尔树的结构，于是只需要拓扑排序即可。

T3，也就说首先暴力的做法就是，对每个位置维护二元组 $(d,b)$，分别表示该位置被多少还没处理的左区间包含，以及该位置当前的限制的最小值。考虑按照值域从小到大处理每个询问，每次取出当前 $d=0$ 的位置，若存在多个则按照 $b$ 从小到大取出，把它的值设置为 $b$，此时我们需要进行更新。

我们需要找到包含这个位置的所有还没有被处理的右区间，则这个位置显然是作为这个区间的 $\min$，同时我们需要把每个右区间对应的左区间找出来，将左区间的每个位置的 $b$ 更新，并把他们的 $d - 1$。

这样暴力做是 $O(nm + n^2)$ 的，我们尝试优化这个过程，首先对于左区间内部的修改和维护最小二元组 $(d,b)$ 可以使用线段树打 tag 来维护，然后考虑把每个右区间拆分成 $\log$ 个区间，对于线段树每个区间维护有哪些右区间跨过了它，对于找到的位置 $v$，只需要访问从叶子到线段树根的路径上所有节点，把这些节点上没处理的右区间对应的左区间进行更新即可，时间复杂度 $O(n+m \log n)$。

吃饭去找了 KSCD_ 和 Iceturky，开心哦。下午去打了球，很舒服。

CF2006E Iris's Full Binary Tree

首先考虑静态如何做，你发现限制条件是，树上每个点度数不超过 $3$，且根节点的度数不超过 $2$。那么你发现对于每个可以作为根的东西，显然深度是距离他最远的点，而这个点是直径的两个端点之一，于是贡献应当是 $r+1+x$，其中 $x$ 表示点到直径中心的距离。

考虑对每个点维护 $x$，你发现加边的过程中，直径的端点与长度变化都是好维护的，从而对于 $x$ 的修改应当是每次把一个子树 $+1/-1$，使用线段树维护区间加区间最小值即可。

11.13 杂题，树上问题

CF2230F Game on Growing Tree

哎呦说实话，这个题，牛大了啊，感觉真神了。

首先你肯定会一个 $O(n^3)$ 的做法，你考虑如果确定了根这个问题是很好做的，因为每次 Bob 必然封堵最优的那条路线，让 Alice 走向相对不那么优的路线，于是可以设计一个 dp，设 $f_u$ 表示考虑 $u$ 的子树，当前 $u$ 已经被染红，轮到 Bob 操作，此时 Alice 能走的最大步数。

考虑转移就是把儿子的 $f$ 全都取出来，此时 Bob 会封堵最大值所在的子树，而 Alice 只能跳到次大值，于是 $f$ 从儿子中次大值转移过来。

先不考虑加点，这个东西显然可以通过换根做到每个静态局面 $O(n)$，于是有一个粗略的复杂度是 $O(n^2)$。接下来你考虑发现一些性质，由于这个东西取到的是次大值，于是只有子树内 $\ge$ 两个位置取到这个值，才能够被更新，从而每个值被更新的次数只会有 $O(\log n)$ 次。

接下来你考虑是否说换根的数组 $g$ 也只会被更新 $O(\log n)$ 次，你发现这个很对啊，考虑一下 $g$ 是如何变化的，对于一个点维护一下前三大的子树信息，分别记成 $a_1,a_2,a_3$，在向某个方向转移时，若该方向恰好为 $a_1,a_2$ 所在的子树之一，则只能取到 $a_3 + 1$，否则取到 $a_2$。

取到 $a_1,a_2$ 的子树只有常数个，考虑如果 $a_2$ 没有改变则除了这两个子树其它的都不需要重算，否则 $a_2$ 变了只能对每个重算，而 $a_2$ 只会改变 $O(\log n)$ 次，因此总时间复杂度 $O(n\log n)$。

AT_arc087_d [ARC087F] Squirrel Migration

这么强？

首先考虑上面那个的结论，把贡献拆给每条边，想要取到贡献的上界，必然要把每个点匹配到与它不在重心的同一连通块的点上，要注意如果只有单个重心则重心这个点允许与自己匹配。

考虑问题转化为把重心每个子连通块染色，求排列 $p$ 的方案数，使得 $p_i$ 和 $i$ 颜色不同。考虑容斥，钦定 $j$ 个配对为相同颜色，最终答案为

$$\sum\limits_{j=0}^{n-1} (-1)^j f_j(n-j)!$$

其中 $f_j$ 就表示选出 $j$ 对相同颜色配对的方案数。考虑如何求出这个 $f$，首先不难对于每个连通块，设该块内共有 $s$ 个点，选出 $j$ 对的方案为 ${s\choose j} ^2 j!$，最后背包合并一下，转移为 $f_{i+j} \leftarrow f_i{s\choose j} ^2 j!$。

然后就做完了，时间复杂度 $O(n^2)$。