09.21 - 09.27 学习记录

发表于 2026-09-23 更新于 2026-10-01 分类于学习记录

09.21

VP CF 1097 Div.2

C

题意

给你两个长度为偶数的括号序列 $a$，$b$，不一定合法。你可以交换 $a_i$，$b_i$，问能否通过交换使得 $a$，$b$ 合法。

$n \le 2\times10^5$

赛时思路

交换相同的是无用的，只会交换不同的。左右括号的数量是不变的。
在扫的过程中不知道到底要不要交换，因此延迟决策。
当 $sum_a<0$ 时，将 $a$ 中的一个左括号变成右括号，此时 $sum_b \leftarrow sum_b-2$。调整其中一个必然会使得另外一个 $-2$，模拟就好了。

D

题意

给你两个长度为 $n$ 的正整数序列 $a$，$b$。随机排列 $b$，定义 $c_i=a_ib_i$，求 $c$ 数组逆序对数量的期望。

$n \le 2000$

赛时思路

我们枚举逆序对数量，统计逆序对 $= x$ 的序列 $c$ 有多少个，这就变成了一个计数问题。感觉不太可做。
注意到 $c$ 数组的取值很少，我们考虑对 $c$ 数组的每一个取值算贡献。
枚举 $i$，$j$，再枚举它能产生多少个逆序对，然后计数。
发现排序能带来一些性质，那就给 $a$ 和 $b$ 先排个序。逆序对有下标约束的，怎么也不能排序吧（
对于每个 $a$，能取的 $b$ 的范围越来越大，这让人联想到之前做过的某道计数题，从小的区间开始取就完了。
记每个 $a$ 能取 $cnt$ 个 $b$，则对于每一个逆序对数 $k$，有 ${n-i\choose k} \prod\limits_{i=0}^{k-1} cnt_{p_i-i}$ 种方案。
这复杂度爆炸了啊，也没有什么优化空间。
那我给 $c$ 的取值排序呢？这个好做欸。
枚举 $a_ib_j$，在所有 $c$ 取值的位置里二分找到它，记其下标为 $p$。对于每一个逆序对数 $k$，有 ${n^2-p \choose k}$ 种方案。但这样有个问题，右边的 $a$ 应该一定大于当前 $a$ 才行。
这个其实好处理，只需要倒序遍历 $a$ +归并排序就可以处理出所有可取的 $c$ 的取值的大小。记当前遍历到了 $a_i$，$b_j$，则右边一共有 $(i-1)\times n$ 种取值，在其中找到有 $cnt$ 个大于 $a_ib_j$ 的。对于每一个逆序对数 $0 \le k \le cnt$，都造成 $k \times {cnt \choose k}$ 的方案数。这个可以前缀和预处理。最后再除以排列总数 $n!$。
于是我们得到了一个 $O(n^2 \log n^2)$ 的解法。这个做法假了啊，这样 $b$ 可能重复取。
把贡献拆到每一个取值上不行，拆到每一个序列上也不行，还能拆到哪啊？
放弃了，用时 $72$ 分钟。

订正

逆序对的期望，往两方面考虑：
1. 值：这就是我的赛时思路，做不出来。
2. 下标：每一对逆序对贡献 $\frac{1}{n(n-1)}$ 的期望，我们统计有多少对逆序对就好了。
  1. 枚举下标 $i$，$j$，要使得 $a_ib_p < a_jb_q$，也就是 $\frac{a_i}{a_j} > \frac{b_q}{b_p}$，给右边预处理出来之后再排序，二分找就好了。

一些思考

因为 $a$ 是确定的，所以我们优先钦定 $a$。

下次做数数题，先想好，有哪些主体可以贡献答案，从小到大。

杂题

ABC 476 G

题意

给你一个区间 $[l,r]$，要求 $a[l…r]$ 满足：

$a_i \ge 1$
若 $a_i = a_j$ 且 $i < j$，则 $\operatorname{popcount}(i) < \operatorname{popcount}(j)$。

要求最小化 $\max a[l…r]$。

$l,r \le 10^{18}, T \le 10^4$

思考

区间长度是上界。
这个 popcount 的约束是关键，如果我能按照 popcount 分类，那怎么做呢。
同一类的取值不能相同，不同类，还得收到下标约束。
这种双关键字偏序问题，可以放到坐标轴上考虑。以 $i$ 为 $x$ 轴，$\operatorname{popcount}(i)$ 为 $y$ 轴，若 $i$ 点左下角有任意一个点，就可以和它取值相同，不更新最大值。
现在的问题就变成了，有多少个点的左下角是空的。这个好像可以做欸。
找到 $f_i$ 表示第一个 $\operatorname{popcount}(x) = i$ 的下标 $x$，然后找前缀最小值的个数就好了。现在的问题就是如何求 $f_i$。
将下标按照 $2$ 的次幂分组，每一组的取值都是有规律的。具体而言，长度为 $2^{i-1}$ 的那一段的末尾（也就是第 $2^i-1$ 个数）的 popcount 就是 $i$。
将 $[l,r]$ 裂成很多段，其中完整的段的贡献好算，不完整的段中，末尾段是没用的，只需要考虑开头段。

订正

这个问题其实是在问，把 $[l,r]$ 之间的数至少串成多少条 popcount 递增的链（同一条链的取值相同），才能将 $[l,r]$ 全覆盖。
根据 Dilworth 定理，最小链划分链数 $=$ 最大反链大小。所以我们求最大反链大小，也就是 popcount 最长不增子序列。
我们来探索一下 popcount 的性质。
popcount 与二进制有关，所以我们尝试将数按照 $2$ 的次幂分类。
1. $[0, 1]$ 产生的 popcount：$0$，$1$
2. $[2, 3]$ 产生的 popcount：$1$，$2$
3. $[4, 7]$ 产生的 popcount：$1$，$2$，$2$，$3$
4. $[8,15]$ 产生的 popcount：$1$，$2$，$2$，$3$，$2$，$3$，$3$，$4$
性质：从 $0$ 开始的，长度为 $2^k$ 的段，前 $2^{k-1}$ 项 popcount 与上一段相同，后 $2^{k-1}$ 项的 popcount 是上一段整体 $+ 1$。
所以我们得到启示，将 $[l,r]$ 按照某种 $2$ 的次幂分段。按照常规倍增的方法跳跃是不行的，因为从 $l$ 开始的长度为 $2^k$ 的段，它不一定具有这样的性质。为了运用我们发现的性质，只能跳跃 $\operatorname{lowbit}(l)$ 及以下的 $2$ 的次幂，因为 lowbit 下面的位是全 $0$。
于是我们预处理 $f_{i,j,k}$ 表示，长度为 $2^i$ 段中，popcount 以 $j$ 开头，$k$ 结尾的最长不增子序列长度是多少。有转移：$f_{i,j,k}=f_{i-1,j,mid}+f_{i-1,mid-1,k-1}$。相当于把两个长度为 $2^{i-1}$ 的段拼在一起，后面的段的 popcount 会因为前面的段而整体右移一位，所以要 $-1$ 。
令 $dp_i$ 表示，popcount 以 $i$ 结尾的最长不增子序列长度。转移时先找到第一个 $\operatorname{lowbit}(l)$ 以下，且 $l + 2^k \le r$ 的 $k$（这其实就是倍增，但是加了 lowbit 的上界约束），然后有：$dp_j=\max\limits_{j\le i}(dp_j,dp_i + f_{k,i,j})$，注意一下循环顺序就好了。
总共的时间复杂度是 $O(\log^4 V+T \log^3 V)$，足以通过本题。

Intervals

题意

给定 $m$ 个区间和它的权值，如果区间内有至少一个 $1$ 就可以获得这个区间的权值。问最大权值和。

$n,m \le 2\times 10^5$，$\vert a_i \vert \le 10^9$

思考

最优化问题，先想一下贪心，最好的情况肯定是正数全拿。只要不被负数区间包含的肯定可以拿。
然后就是一些负数包裹着正数的区间。发现变得很复杂，不可做了，那就考虑 dp。
令 $f_i$ 表示只考虑左端点小于 $i$ 的区间，前 $i$ 项能得到的最大权值。
1. 选 $i$ 点：推不出来，主要原因是区间与区间有复杂的包含相交关系。
2. 不选 $i$ 点：$f_i=f_{i-1}$
那我以区间为阶段进行 dp 呢？先把区间按照右端点排序。$f_i$ 表示前 $i$ 个区间的最大收益。
1. 不选 $i$ 区间：$f_i=f_{i-1}$
2. 选 $i$ 区间：还是不会推（

正确思路

定义 $f_i$ 表示，$i$ 点强制选的最优价值。
1. 设上一次选的位置是 $j$，只有 $j < l \le i \le r$ 的区间才会贡献 $a_i$。
2. 那我们维护一个活跃集合 $s$，当 $i=l$ 时将区间加入集合，$i=r+1$ 时将区间移出集合。
3. 枚举 $j$，当 $j$ 等于活跃集合里某个区间的 $l$ 时，将这个区间的贡献删掉，记当前活跃区间贡献为 $cnt$，则有：$f_i=f_j+cnt$。时间复杂度 $O(n^2+nm)$。
考虑优化转移。
1. 定义 $g_j$ 表示从 $j$ 转移过来的价值。
2. 加入一个区间进入活跃集合：所有的 $j < i$ 都加 $a$
3. 删除一个区间进入活跃集合：所有的 $j < l$ 都减 $a$
4. 线段树维护 $g$ 就可以了。时间复杂度 $O((n+m) \log n)$

一些思考

本质上是在用线段树维护转移集合。

树论专题

三目运算

题意

给你一串三目运算，$q$ 个询问，问 $x$ 会返回多少。

思考

一眼看上去感觉要建表达式树啊。
递归建树。
1. 如果以 $x$ 开头，记录时大于号还是小于号，数字是多少。然后找到每个 ? 对应的 :，? 后面的是左儿子，: 后面的是右儿子。
2. 如果不是以 $x$ 开头，返回数字。
询问的话就是跑一遍这个树就好了。

正确思路

真是小看这题了，直接查询的话时间复杂度会炸，需要预处理。
预处理的时候维护一个 $[l,r]$ 区间，表示这个区间内的数的结果都是相同的，然后不断分化就好了。

一些思考

第二次见到维护值域区间这个技巧，感觉还挺好用。

改造二叉树

题意

给你一棵 $n$ 个节点的二叉树，$1$ 为根，点有点权。操作可以修改一个点的点权，要使其点权满足二叉搜索树的性质，问最少要修改几个节点？

$n \le 10^5$

思考

最优化问题，先想一下 dp。
很快就能想到一个树形 dp。$f_{i,0/1}$ 表示，以 $i$ 为根的子树满足二叉搜索树性质，且 $i$ 比 $fa_i$ 小/大的最小操作次数。但是转移不了啊。
想一下贪心？把不满足二叉搜索树性质的节点找出来，没啥用啊。

正确思路

需要利用二叉搜索树中序遍历是严格升序的性质做这题。没有利用结构性质的意识啊
将这课二叉树的中序遍历存起来，现在要修改最少的点使其变成严格升序。
经典结论：将不降序列 $a$ 的第 $i$ 项 $+ i$ 后，会变成一个严格升序序列。涉及到严格增减时这个结论异常好用啊，第三次见了
于是我们反过来，将 $a_i\leftarrow a_i-i$ 后，进行最少修改，使其变成一个不降序列（这等价于找最多能保留多少个数）。
这个是好做的，求出最长非降子序列就好了。

一些思考

写着写着发现自己对贪心求 LIS 有了新的理解。这个方法是基于 Mirsky 定理的。这个定理是在说：

最长链的长度 $=$ 覆盖所有元素所需的最少反链数。

LIS 本质上是求最长链长度，贪心解法本质上就是在求最少反链数。

09.22

板刷 CF

2257E

题意

你有 $x$ 元，$n$ 栋楼，每栋楼有 $j$ 层。建完下层才能建上层。建某栋楼需要花费 $a_{i,j}$ 元，得到 $b_{i,j}$ 元。

要使得某栋楼尽可能高，输出这栋楼的高度和下标。

$\sum m \le 10^5$，$x \le 10^{18}$

赛时思路

一个自然的贪心是，钦定最高的那个楼层，其它楼层都取最大收益。
但这个最大收益不好确定，因为可能牵扯到其他楼层。感觉最终需要 dp 做，但是需要一些贪心的性质。
试着暴力做这个找最大收益的过程。
1. 对当前 $x$ 处理处每个楼层的最大收益。其实还是思维有漏洞吧，这里想到最大收益是没道理的。只有说选择有代价的时候才会这样想。
2. 选择收益最大的那个，循环往复。
3. 如果最大为负则跳过。
4. 暴力做法的瓶颈在于，因为 $x$ 的改变，同一个元素会被遍历多次。
5. 实际上不需要吧，因为 $x$ 是单增的，是不是可以用双指针维护呢？显然是可以的。
6. 这样子的话时间复杂度 $O(\sum m+n \times \sum m )$。这里的瓶颈在于，需要去通过遍历找最大收益。根本的误区在于，不需要最大收益，只需要收益为正就好了。如果意识到这点，这题就做出来了。
7. 然后发现只要收益是正的，选它一定不劣。但是也没有什么优化。因为选择正收益一定不劣，所以处理出每个楼的最短且收益为正的段数，按照“门槛”排序就好了啊。
现在有两个方向：
1. 用某种算法加速这个暴力
2. 换思路
  1. 首先如果这题的大楼一定要按顺序建，那么这就是一个简单的贪心。$O(\sum m)$ 搞定。
  2. 问题就出在，它建楼的顺序不受限制，导致 dp 转移没有 topo 序。
  3. 那我们就人为添加一层状态，使其满足 topo 序不就好了？
  4. $f_{i,j}$ 表示，已经建了 $i$ 层，剩下 $j$ 元可不可行。这还是转移不了，因为受到楼层约束。
  5. 不可能记录下所有楼层的信息，但是转移又需要用到，说明一定是缺了一些贪心的性质。
感觉没戏了，用时 $50$ 分钟。

订正

这种多个序列，从中取数的问题，通常每个序列会有一个指针，通常还有一个优先队列。
我们考虑模拟这个过程。我们现在先把最大收益拿到，再钦定哪栋楼是最高的。
怎么拿最大收益呢？发现拿一段非负的段一定是不劣的，所以我们每次就拿极短非负段。
这些段拿起来会有一个“门槛”，把所有段按照门槛排序，拿到不能拿为止。每拿一段，对应的那个序列就向后找一个极短非负段，每个点最多被遍历一次，时间复杂度 $O(nm \log n + nm)$。

一些想法

感觉自己做题比较依赖直觉和灵感，对这种需要不断尝试的题目耐性不大啊。其实多想一会儿说不定还是能做出来的。

而且思维也有漏洞，可以多想一想这步这到底对不对。

2252E

题意

统计一下三元组 $1 \le a < b < c \le n$ 的数量，要求：

$b-a=c-b$
$a \oplus b \oplus c=0$

$n \le 10^{18}$

赛时思路

分析约束
1. 异或和约束：说明三个数的二进制里，每一位都只有 $0$ 或 $2$ 个 $1$。
2. 和约束：$a+c=2b$。
从异或和约束出发，考虑二进制每一位怎么填。
1. 填 $0$ 好说。
2. 给 $b$ 和 $a/c$ 填 $1$：下一位一定是给 $a,c$ 填 $1$，否则必然不满足当前位和约束。
3. 给 $a,c$ 填 $1$：上一位一定是给 $b$ 和 $a/c$ 填 $1$，下一位不能填 $a,c$，否则必然不满足当前位和约束。
为了满足大小约束，第一步一定给 $c$ 和 $b$ 填 $1$，第二步一定给 $a,c$ 填 $1$，然后再怎么填也不会改变大小关系了，自由填就好了。每一次填都能满足当前位的和约束，所以一直填到底，只要能填出来，就是合法的。
可以做一个类似数位 dp 的记忆化搜索。
还有 $n$ 的约束。啊啊感觉非常复杂，能不能把这个东西变成一个简单的过程呢？
力竭了，用时 $50$ 分钟。

订正

思路是对的，但是码力太差了写不出来。
按位考虑，$\text{lim}$ 表示受不受到 $n$ 约束，$\text{fir}$ 表示有没有第一个 $1$，$x$ 表示第几位，

树论专题

笛卡尔树

构造一棵笛卡尔树。按照下标顺序插入节点，因为 BST 的性质，新插入的节点一定是最右节点。

因此不断弹出右链上节点，遇到 $w_v < w_u$，就把 $u$ 接到 $v$ 的右儿子上，$v$ 的右儿子接到 $u$ 的左儿子上，用单调栈维护。

树的序

题意

从一个空树开始，插入一个 $[1,n]$ 排列，形成一棵二叉搜索树。

问能形成同一棵二叉搜索树的字典序最小的排列。

$n \le 10^5$

思考

我们先把题目的 BST 建出来，然后逆向。
找到生成左子树和右子树的序列后，比较一下哪个放前面字典序小就好了。
但是这样会 TLE，考虑优化。
注意到右子树都是比左子树大的数，所以左子树放开头一定更优。
？这不就是先序遍历吗，被诈骗了。。
然后瓶颈在于建树。

正确思考

值满足二叉搜索树限制，如果把插入顺序看作关键字，则满足堆性质。
这不就是笛卡尔树吗？？？
仿照笛卡尔树的过程，将 $a$ 按照值排序。这样每插入一个点，它都一定在最右下方。
然后就是单调栈。时间复杂度 $O(n \log n)$。

Yet Another Array Counting Problem

题意

给你一个长度为 $n$ 的序列 $a$，取值范围 $[1,m]$。

问有多少个序列 $b$，满足对于任意的 $1\le l \le r \le n$，$b[l…r]$ 和 $a[l…r]$ 的最左边的最大值的下标都相同。

$n\times m \le 10^6$

思考

先确定最好确定的。$a$ 中的最大值，在 $b$ 中也一定是最大值。那么这个最大值将整个序列分成了左右两段（因为跨越 $i$ 的约束都被 $i$ 满足了，只用去左右继续满足约束了），再去这左右两段递归找最大值就好了。
组合数学计数，每次找到区间的最大值之后，枚举这个取值，乘法原理就好了。时间复杂度 $O(n^2m)$。
但如果我直接建一棵笛卡尔树，然后树形 dp。$f_{i,j}$ 表示，以 $i$ 为根的子树，最大值为 $j$，能产生多少种序列。转移时，枚举 $j$，则有：$f_{i,j}=\sum\limits_{k=1}^{j-1} f_{lc,k}\times\sum\limits_{k=1}^{j} f_{rc,k}$，直接维护前缀和可以做到 $O(1)$ 转移。总时间复杂度 $O(nm)$，空树贡献 $1$。

后记

这个 “先找到最好确定的，然后将序列分成两半” 的技巧已经是第二次见了。
这种 “找到左/右” 第一个 $<$ 我的下标的结构，要联想到笛卡尔树。

09.23

板刷CF

2248E

题意

给你三个整数 $n,m,d$ 和两个长度为 $m$ 的数组 $p,r$，$p$ 严格增。

定义一个 $01$ 序列 $a$ 的价值为 $f(a)$，计算过程如下：

若 $a_i=1$，则 $v \leftarrow v+d, c\leftarrow c+1$
否则 $c \leftarrow 0$
然后若 $c=p_j$，则 $v \leftarrow v+r_j$
若 $c=n$，则 $c \leftarrow 0$

问是否存在某个 $a$ 序列，使得 $f(a) >\underbrace{ f(11\cdots111)}_{\lvert a \rvert 个 1}$

$m \le 2000$，$n,d,p_i,r_i \le 10^9$

赛时思路

一个比较自然的想法是，构造一个 $a$ 序列尽可能多达到 $p$。因为唯一能拉开差距的地方就是 $p$ 了。
$f(11\cdots111)=d \times \vert a \rvert+\sum r_j [p_j \le \lvert a \rvert \bmod n]+ \frac{\vert a \rvert}{n} \times \sum r$
$a$ 的结构一定是很多个全 $1$ 序列，用 $1$ 个 $0$ 分隔开来（多个 $0$ 一定不比 $1$ 个 $0$ 优）。$a$ 可以选择很多个 $r$ 的前缀，全 $1$ 序列只能选择所有 $r$，这就是 $a$ 和全 $1$ 序列的区别。
猜测 $a$ 一定会贪心选择那个上升最 “剧烈” 的前缀，即 $\frac{\sum r}{\sum p}$ 最大的那个。但是越短的前缀 $-d$ 的次数就越多。
函数应该是有周期的。如果在第一个周期里没有超越，之后就不可能了。
感觉没想到点上，放弃了。

订正

结论是，如果 $S_x+S_y > S_{x+y+1}$ 就一定可超越，否则不行。
考虑 $S_x+S_y \le S_{x+y+1}$ 的情况，此时将两段全 $1$ 序列合并一定不亏，所以会一直合并，直到变成全 $1$ 串。
由于只有当 $x$ 跨越 $p$ 的时候会有变化，所以 $O(m^2)$ 就可以完成判断了。

2238E

题意

博弈题。给你一个长度为 $n$ 的字符串 $s$，有 T，F 和 N。$A$ 需要将 N 替换成 T 或 F。

$B$ 需要选择一个区间，定义它选择的代价为：区间内的 T 数量和区间外的 F 数量。

$A$ 希望这个代价尽可能大，$B$ 希望代价尽可能小。

$n \le 500$

赛时思路

感觉这题需要先考虑 $B$ 的策略。
1. 考虑一开始不选。
2. 选择一个区间后，$\Delta=区间内 T 数量-区间内 F 数量$。
3. $B$ 会尽可能使得这个变化量最小。如果把 $T$ 当作 $1$，$F$ 当作 $-1$，那么 $B$ 就会选和最小区间。
4. $总代价=F的数量+最小区间和$
然后考虑 $A$ 的策略。
1. 总代价有两部分，我们可以试下分别钦定这两个。
2. 钦定 $F$ 的数量。
  1. 现在的目的是令区间最小值尽可能大。
  2. 感觉不好做，换过来吧。
3. 钦定最小区间和。
  1. 现在的目的是令 $F$ 的数量尽可能多。
  2. 这个也不好做啊。
没招了。

订正

有两种做法：

钦定 $F$ 的数量，也就是 dp。
1. 错误做法
  1. 常规的 $f_{i,j,0/1}$ 表示，前 $i$ 项，$i$ 选不选，用了 $j$ 个 $F$ 能到达的最小区间和是多少。
  2. 但这样会产生一个问题，$f_{i,j,1}$ 和 $f_{i,j,0}$ 维护的不是同一个局面，因为 $f_{i,j,1}$ 维护的是“从 $i$ 开始向前的一段”区间最小，而 $f_{i,j,0}$ 维护的则是全局最小，这两个 dp 的目的不同，所以不能相互转移（即保证从 $i$ 开始向前的一段区间最小，反而可能会使得全局最小区间更大）。
  3. 解决办法就是将 $f_{i,j,0}$ 当成 $f_{i,j,1}$ 的一个状态。
  4. 具体地，令 $f_{i,j,k}$ 表示：前 $i$ 项，选了 $j$ 个 $F$，并且从 $i$ 开始往前选地区间最小值为 $k$ 的全局区间最小值。这样子 dp 的目的就统一了。
钦定区间和，反悔贪心。
1. 从前往后钦定区间右端点，遇到 N 就改成 F。没有钦定的意识吧。
2. 然后从后往前钦定左端点，如果区间和 $< x$，那就将最右边的 N 改成 T，区间和 $+2$。
3. 改靠右的 $N$ 一定是不劣的。因为对于以当前 $r$ 为右端点的区间来说，改哪里都是一样的；对于右端点 $< r$ 的区间来说，它们已经是合法的了；对于右端点 $> r$ 的区间来说，你改的越靠后，它们增加的就越快，需要修改的风险也越少。

2234F

题意

$n$ 个空心柱子排成环，$i$ 和 $i \bmod n +1$ 之间被一个高度为 $h_i$ 的横柱连在一起。

问，对于每个 $i \in [1,n]$，令 $i$ 中没有水，其他柱子能装的最多的水是多少。

$n \le 2\times10^5$

赛时思路

先考虑链的情况。处理出每个柱子在水不能流出去的前提下，最多能装多少水 $a_i=\min(h_{i-1},h_i)$。钦定 $i$，左右遍历，取 $a_i$ 前缀最大值填。第一步就错了啊，思维缜密一点。
环的问题在于，最左和最右需要联通。
1. 如果 $h$ 高于两边的水位，那自然没问题。
2. 如果 $h$ 低于两边的水位
  1. 如果水位高度相等，也没问题。
  2. 如果高度不等就 GG 了。
考虑环的解法。
1. 钦定 $i$，此时变成了一条链。
2. 对于每一个 $i$，找到右边第一个 $> a_i$ 的数，这段区间都填 $a_i$。
3. 这样我们得到了 $O(n^2)$ 的做法，但我们需要一个 $O(n \log n)$ 的做法，考虑优化。
环解法的优化
1. 两种优化的方向
  1. 我们或许不需要钦定每一个 $i$，因为很多答案都是重复的。
  2. 钦定 $i$，但是用双指针之类的技巧优化求解的过程。
2. 尝试第二种方向
  1. 扩环成链，移动长度为 $n-1$ 的区间。
  2. 每加入一个点，更新一些点的 $r_i$。每个点只会被更新一遍。
  3. 每删除一个点，$r_i$ 以后的点没有变化，所以从 $i+1$ 开始跳，一直跳到 $r_i$。这样保证每个点只会被跳到一次。
  4. 总共时间复杂度 $O(n)$。
具体流程
1. 处理出 $a_i=\min(h_{i-1},h_i)$，复制一份，扩环成链。
2. 算出 $ans_1$，维护 $r_i$ 表示右边第一个 $> a_i$ 的数。没有就设成 $i+1$。
3. 然后从 $3$ 开始滑动窗口，先用 $i+n-1$ 这个点更新 $r_i$，然后再从 $i$ 点开始跳，一直跳到 $r_{i-1}$ 为止，这里可以写个函数。
4. 最后记录输出答案。
被样例 hack 了（悲。好像一开始的暴力就是错的。

订正

把 $h$ 抽象成柱子，那么水只能在柱子之间的“洼地”之间流淌。
断成链之后，两端的水源会在中间最高的那个地方汇聚。
定义 $f_i$ 表示，从 $i$ 开始填，一直填到结尾，能填多少。转移：$f_i = f_{r_i}+(r_i-i)\times a_i$，$g$ 则是它的逆向。
滑动窗口时，记最大值下标为 $id$，则它的 $sum=f_l-f_{id}+g_r-g_{id}$。非常巧妙啊，用前缀和优雅的解决了这个问题。下一遇到问题可以想一想能不能前缀和解决。

09.24

板刷 CF

2237D

题意

给你一个长度为 $n$ 的 $01$ 串 $s$，每次操作可以使 1 替换 00，0 替换 11。问 $s$ 有多少个子串最后能被替换到只剩下一个字符。

$n \le 10^6$

赛时思路

首先暴力是容易的，一个 $O(n^2)$ 的区间 dp。
研究一下操作的性质：
1. 先来考虑对一个字符串，如何判断它是否满足条件。
2. 记 $0$ 的数量为 $c_0$，$1$ 的数量为 $c_1$，$c = c_0-c_1$
3. 每次操作 $c$ 都会增加 $3$ 或减少 $3$，最终变成 $1$ 或 $-1$，所以若 $c \bmod 3=0$ 则一定无解。
4. 猜测，所有 $c \bmod \ne 0$ 的字符串一定可以满足条件。反例：010。
5. 给字符串按照相邻相同缩点。如果长度是偶数，则剩下 $n/2$ 个相反字符，否则多剩下一个相同字符。没啥用。
6. 考虑按照 $c$ 的取值分类讨论：
  1. $c \bmod 3= 0$，无解
  2. $c \bmod 3= 1$，最后剩下 $1$ 个 $0$。没什么用。
7. 至少根据 $c$ 的取值，我们确定了：一个字符串最终只可能是无解，$1$，$0$ 这三种情况，不可以既是 $0$ 又是 $1$.
刻画一下合法字符串长啥样：0，11，001，0000。没什么用。
刻画一下非法字符串长啥样：$0$，$1$ 个数差等于 $3$ 的倍数；01010101...。
1. 好像只有这两种情况是非法的？
2. 那我们就容斥一下嘛。
3. 前者可以通过前缀和统计，后者可以通过缩段统计。注意不要记重了。
真的过了（笑。用时 $54$ 分钟。

2237E

题意

给你一个长度为 $n$ 的排列 $a$，和一个不完整的排列 $b$，未填部分用 $-1$ 代替。

求一个字典序最小的 $b$，使得 $a_{b_i}=b_{a_i}$，可能无解。

$n \le 2\times 10^5$

赛时思路

感觉非常复杂啊，看了 $10$ 多分钟样例还是没看出有啥性质。
先来考虑简单的情况：
1. $b$ 全是 $-1$：此时 $b$ 填 $1234…$ 一定满足要求？为什么呢？
  1. 因为此时 $b_i=i$，所以 $a_{b_i}=b_{a_i}$ 就可以变形成：$a_i=a_i$，恒成立。
再观察样例，发现，把那些能确定的点都确定完之后，剩下的 $-1$ 就是 $12345…$ 这样填？遇到相等的就退出，不相等就无解。这个是不是和置换环有什么关系啊？
交上去 WA 了。用时 $41$ 分钟。

订正

这题要用到群论相关知识了，先鸽掉吧。

2237F

题意

定义一次涂色操作为：将 $i \in [l,l+m-1]$ 涂上 $l-i+1$。

给你一个长度为 $n$ 的序列 $a$，问至少修改其中的几个数，会使得 $a$ 可以由涂色得到。

$n \le 5\times 10^5$

赛时思路

先来考虑如何判定一个序列是不是涂色序列
1. 相邻两数最多上升一格。这里就推错了，感觉还是举反例的能力不够强，而且思维也不够缜密吧。
2. $a_i \le i$，$a_i \le m$ 其实我这里的思路更偏向于解法 2，但判断依据还是没搞对。
我们现在就要修改序列，使其满足以上两个条件。最优化问题，很自然地会去考虑 dp。
1. 令 $f_{i,j}$ 表示，前 $i$ 项，以 $j$ 结尾，最少需要修改多少个数。就算是想错了这里的 dp 也不是这样定义，参考树状数组求 LIS 的方法。
2. 转移：
  1. $f_{i,a[i]} = \min \limits {a[i]-1 \le j\le m}f{i-1,j}$，前提是 $a_i \le i$
  2. $f_{i,j} = \min \limits {j-1 \le k\le m} f{i-1,k}+1$，前提是 $j \le i$
  3. 每次转移都依赖上一层的后缀最小值。轻松得到 $O(n^2)$ 的做法。
3. 优化转移
  1. 如果没有 $a_i$ 这一项，那么整个 $f_i$ 就是单调增的。
  2. 也就是说，我们可以得到：
    1. $j-1>a_{i-1}$，$f_{i,j}=f_{i-1,j-1}+1$
    2. $j - 1 \le a_{i-1}$，$f_{i,j}=\min(f_{i-1,j-1},f_{i-1,a_{i-1}})+1$
    3. $j = a_i$，$f_{i,a[i]} = \min \limits {a[i]-1 \le j\le m}f{i-1,j}$
  3. 找到第一个 $k \le a_{i-1}$ 使得 $f_{i-1,k} \le f_{i-1,a_{i-1}}$，又可以将第二条转移分成 $2$ 段，这个可以线段树上二分。
    1. $f_{i,[k+1…a_{i-1}+1]}=f_{i-1,a_{i-1}}+1$
    2. $f_{i,[1…k]}=f_{i-1,j-1}+1$
  4. 如果 $f_{i,j}$ 是从 $f_{i-1,j}$ 转移而不是 $f_{i-1,j-1}$ 转移这题就结束了。可恶。
用时 $50$ 分钟。

订正

解法 1

先来考虑如何判定一个序列是不是涂色序列。
1. 对于任意一个下标 $i$，满足：
  1. $a_i \le i$
  2. $m-a_i+i\le n$
2. 对于任意两个下标 $i,j$，它们满足下列条件之一：
  1. $i,j$ 同处一个块：$i-a_i=j-a_j$
  2. $i$ 的块不覆盖 $j$：$i-a_i < j-m$
  3. $j$ 的块不覆盖 $i$：$i\le j-a_j$
3. 如果 $i,k$ 满足，$k,j$ 满足，则 $i,j$ 满足。
然后要求尽可能少修改，就是尽可能多的保留。被修改的点无论如何都是合法的。
1. 定义 $f_i$ 表示，前 $i$ 项，第 $i$ 项一定保留，最多保留多少个。这个状态好常见啊。
2. 转移就根据上面那个合法情况来，而且只需要找最大的那个。具体地：
  1. 打在 map 上
  2. 打在树状数组上。树状数组可以维护前缀 max，前提是单调修改需要不降。
  3. 维护 $f$ 的前缀 max。

解法 2

同样地考虑如何判断是否合法，这次我们换一种思路
1. 对于相邻两项，只需要满足以下条件之 $1$ 就一定可以构成合法序列：
2. $a_i=1$，$a_i=a_{i-1}+1$
3. $a_{i-1}=m$
修改序列使其满足以上条件，考虑 dp。
1. 定义 $f_{i,j}$ 表示，第 $i$ 项填 $j$ 的合法序列最少修改次数。
2. 转移：
  1. $f_{i,j}=\min(f_{i-1,j-1},f_{i-1,m})+[j\ne a_i]$
  2. $f_{i,1}=\min f_{i-1,j} + [a_i \ne 1]$
  3. 时间复杂度 $O(nm)$。
3. 考虑优化。
  1. 关键洞察：对于 $f_{i,j}=f_{i-a,j-b}$ 的转移，我们可以将其拍成一维。令 $c_i=b·i-a·j$，则 $f_{i,j}$ 可以直接继承 $f_{i-a,j-b}$ 的状态（注意每一行在一维数组上的范围就好了）。
  2. 所以这题的 $c=i-j$，维护一个一维数组 $f_k$ 表示 $k=i-j$ 的状态的最小修改次数，有转移：
    1. $f_k= \min(f_k,f_{i-1-m})+[i-k \ne a_i]$
    2. $f_{i-1}=\min f_{i-1-[1,m]} + [a_i \ne 1]$
  3. 只需要维护单点修改，区间查 min，区间取 min 就可以了，区间 $+1$，如果一开始维护 max 的话就不需要区间 $+1$ 操作。

图论专题

通往奥格瑞玛的道路

题意

$n$ 点 $m$ 边的图，点有点权，边有边权，初始血量为 $b$。

要求找到一条路径，使得其总代价不超过 $b$ 的同时，点权最大值最小。求这个值。

$n \le 10^4$，$m \le 5\times 10^4$

思考

最短路套个二分答案吧。二分出这个点权，只能走点权 $< x$ 的点，然后跑 dij。时间复杂度 $O(\log V \times (n\log n) + m) $。

01 Balanced

题意

构造一个长度为 $n$ 的字典序最小的 $01$ 串，满足 $M$ 个约束：

$[L,R]$ 之间的 $01$ 数量相等

$n \le 10^6$，$m \le 2\times 10^5$

思考

这题好像见过，差分约束来着。
字典序最小意味着尽可能多用 $0$。
如果将 $0$ 视作 $-1$，$1$ 视作 $1$，则 $[L,R]$ 之间 $01$ 数量相等就等价于区间和为 $0$。
区间和问题通常在前缀和上考虑，意味着 $s_{l-1}=s_r$。
$s$ 的字典序最小也意味着原数组的字典序最小。
相邻两项的 $s$ 差值等于 $1$。

正确思路

总结一下 $s$ 的约束：

$s_{l-1}=s_r$
$\vert s_i-s_{i-1}\vert =1$

相等/不等关系下最优化，考虑差分约束。

约束 $1$ 好连边，约束 $2$ 可以将 $i$ 与 $i+1$ 连一条边权为 $1$ 的双向边，因为 $i$ 和 $i+1$ 的取值是不可能相同的（只有同奇偶的位置才可能相同）。

那怎么解决字典序最小呢？原序列的字典序最小，意味着尽可能用 $0$。

所以我们将 $0$ 视作 $1$，$1$ 视作 $-1$。因为前缀和序列的字典序最小等价。前缀和的取值又反应在差分约束图上，这意味着我需要令标号越小的点的 dis 最大。这就是求上界，恰好最短路也是求上界。

如果将 $0$ 视作 $-1$ 的话相当于让 dis 最小，这就是最长路了。时间复杂度不优。

09.25

图论专题

Minimum Path

题意

无向连通带权图，定义路径代价为：$\sum w - \max w + \min w$，求 $1$ 到 $i \in [2,n]$ 的单源最短路。

$n,m \le 2\times 10^5$

正确思路

特殊边权的最短路。
除了特殊化问题，还可以 一般化问题。
这题可以一般化为：选一条边免费，选一条边双倍。由于最短路的性质，这个问题和题目是等价的。
于是我们直接建分层图就好了。
1. 第一层：既没有免费也没有双倍
2. 第二层：免费
3. 第三次：双倍
4. 第四次：既免费又双倍

Shortest Path

题意

给你一个无向连通图，边权为 $1$。不能连续经过一些 $3$ 元组，

求从 $1$ 到 $n$ 的最短路径，要求输出这个最短路径。

思考

带限制的最短路。
给最短路多设一层状态，$dis_{i,j}$ 表示，$i$ 号点，从 $j$ 转移过来的最短路径。
直接 bfs。

Elden Ring

旧题重做。

题意

给你一个连通无向图，点有点权。每天 BOSS 等级增加 $B$，每击败一只 BOSS 玩家等级增加 $A$。

问击败第 $n$ 个 BOSS 所需的最短天数。

$n,m \le 10^6$

正确思考

$A > B$：
1. 发现很难贪心，于是尝试动态规划。设 $f_i$ 表示到达 $i$ 点所需的最少天数。
2. dp 分两种，填表法和刷表法。不是 DAG 上的 dp 基本都是刷表法，类 dijkstra 的那种。
3. 于是这题我们也使用刷表法算。
$A \le B$：只能一路往前走，优先队列跑一遍就好了。

09.26

图论专题

墨墨的等式

题意

给定一个长度为 $n$ 的整数序列 $a$，$b$ 的取值在 $[l,r]$ 之间，问有多少个 $b$ 使得 $\sum a_ix_i = b$ 的同时 $x_i \ge 0$。

$n \le 12$，$0 \le a_i \le 5\times 10^5$，$l,r \le 10^{12}$

思考

先来考虑对于一个 $b$，如何判定是不是合法的：
1. 问题其实是在问，$b$ 能否被分解成 $a_i$ 的和。
2. 用一个 bool 数组存储哪些点可以被拼出，看看 $b$ 能不能被拼出就好了。
考虑每个数能拼出多少个 $b$，只需要看 $< a_i$ 部分哪些点可以被分解就好了。所以就按照 $a_i$ 分段。然后看 $l$ 处在哪个段，$r$ 处在哪个段，中间有多少个段。

正确思路

看到区间计数，要立马想到前缀和。现在的问题转化为，$[0,r]$ 区间内有多少个 $b$。
这个问题可以用完全背包拼数解决，但是值域特别大。
回顾同余最短路的识别技巧：重复加数+值域很大+集合和模数很小。这题明显是同余最短路。
同余最短路的关键在于压缩状态，如果 $i$ 能被拼出，则 $i+ka_i$ 也能被拼出。
所以我们按照最大的那个 $a$ 将序列分段。记录下到达每个余数是在哪一段里被第一次访问。
将 $i$ 与 $i+a_j$ 连边即可，若跨越模数则边权为 $1$，否则为 $0$。
01 bfs，时间复杂度为 $O(A + nA)$。

Jzzhu and Cities

题意

$n$ 点，$m + k$ 条边的无向带权连通图，$m$ 条普通边，$k$ 条从 $1$ 出发的边。

现在要在从 $1$ 出发到达各个点的最短路不发生变化的前提下，删掉最多的从 $1$ 出发的边，问最多删几条。

$n,k \le 10^5$，$m \le 3\times10^5$

思路

考虑删除一条边后，哪些点对的最短路可能受影响：显然是最短路路径里用到了 $(1,s)$ 这条边会受到影响。
删边难想加边易，我们尝试加边。考虑对于两个点来说，它们的最短路径如何变化。
1. 按照边权从小到大加边。
2. 猜测：当两个点被松弛一次后，再也不会被后面加的边松弛。
  1. 被松弛之后，最短路径形如：$u \to 1 \to s \to v$。
  2. 好像证不出来。
3. 题目特殊的地方在于，只会加从 $1$ 出发的边。

正确思路

解法 1

看错题了，只要求从 $1$ 出发的最短路不发生变化。
考虑在什么情况下可能删除一条边（松约束）：
1. 当 $w>dis[v]$ 时
2. 当 $w=dis[v]$ 且不止 $1$ 条到达 $v$ 的最短路时
当满足以上两个条件后，一定要删除这条边（紧约束）。证明：这种先列出一些显然的“松约束”，然后发现它是“紧约束”的题目还是挺常见的。下次做题的之后可以多做一点这种“显然”的事情，多碰一碰说不定就出来了。
1. 当 $w>dis[v]$ 时显然成立
2. 尝试举反例，发现举不出来。
所以最短路计数就好了。

解法 2

这道题目实质上是在问：使用特殊边最少的一棵 最短路树，使用了多少条特殊边。
因此我们 dijkstra 的时候，尽可能不使用特殊边，看最后用了多少条就好了。

模拟赛赛后复盘

时间安排非常合理，前 $2$h 读题想题，后 $2$h 写代码+优化，能达到的分都拿到了（如果有大样例的话）。

一开始被 T1 肘飞也没有慌张，倒序开题，最后 A 了。可能代码细节还是差点。？

挺不错的，下次保持这个节奏。

每一道题最多思考 $30$ 分钟，如果 $10$ 分钟内没进展就停，从部分分开始考虑。

09.27

补题

数字递增

题意

给出 $x$，$n$，$m$。每一天 $x \leftarrow (x+big(x))\bmod m$，问第 $n$ 天 $x$ 是多少。其中 $big(x)$ 表示 $x$ 最大的数位。

$n,m \le 10^{18}$

数字递增 - 题目详情 - 深圳实验中学 OJ

正确思路

关键洞察：
1. 发现 $x$ 的变化可以表达为一棵内向基环树。
2. 每次的变化量最多是 $9$。
  1. 越过 $m$ 之后，只可能是 $[0,8]$。
  2. 从 $[0,8]$ 出发，想让 $x$ 变成 $100000x$，那么，变化之前一定是 $99999x$ 这样的。
解题思路。
1. 体会过程：$x$ --> 第一次越过 $m$ —> $[0,8]$ —> 越过 $m$ —> $[0,8]$ …
2. 先解决从 $[0,8]$ 出发越过 $m$ 的部分：
  1. 由洞察 2.2，从 $[0,8]$ 出发，让 $x$ 的某一位 $+1$ 之后，末尾还是 $[0,8]$。这本质是重复的，让人联想到数位 dp。
  2. 于是我们尝试计算，令 $x$ 的第 $i$ 位 $+1$ 需要多少步数。为了达成这个目的，我们还需要记录第 $i$ 位及其以上的位数的数位最大值，以及末尾是 $[0,8]$ 中的哪个。
  3. 形式化地，令 $f_{i,j,k}$ 表示：从 $k$ 出发，要使得 $x$ 的第 $i$ 位 $+1$，且 $i$ 位及以后的高位的最大值是 $j$ 所需的步数，以及转移之后的末尾元素是多少。
  4. 转移：$f_{i,j,k}=f_{i-1,\max(j,cnt),p}$，$p$ 是不断更新的末尾值，这个转移需要重复 $10$ 次，$cnt$ 是重复次数。
  5. 边界：$i = 0$ 时返回次数 $1$ 以及末尾元素 $now+mx$。
  6. 这一部分记忆化搜索填表，时间复杂度是 $O(10^3 \log n)$ 的。
  7. 然后从高到低，看这一位能不能 $+1$，能 $+1$ 就 $+1$，否则递归处理下面的。
3. 然后解决从 $x$ 出发到第一次越过 $m$ 的部分。
  1. 同样地，从高往低计算令 $x$ 第 $i$ 位 $+1$ 所需要的次数，以及 $+1$ 之后的末尾元素。
  2. 如果可以 $+1$ （没越过 $m$ 且次数足够），那就一直 $+1$，否则就递归处理下面的元素。
  3. 由于 $+1$ 一次之后末尾一定变成 $[0,8]$，所以不能记忆化的部分是一条链，总共时间复杂度 $O(\log^2 n)$。
4. 然后处理环。
  1. 当前起点是 $[0,8]$，然后根据预处理的第一次越过 $m$ 的值，往后跳环，直到遇到相同元素。
  2. 环长至多为 $8$，非常快速。
5. 总结一下：
  1. 需要处理一个 a2 的 $f$ 数组，一个预处理函数。
  2. 需要一个 a2 的 cal 函数，用于计算从 $s$ 出发，走 $n$ 步，不能越过 $m$ 最多能走几步，以及 $s$ 变化后的取值。

宝藏解锁

题意

护照 / Passport - 洛谷

给你 $n$ 个未解锁的宝箱，可以通过拿走已解锁的宝箱 $i$ 中的金币，解锁 $[l_i,r_i]$ 的宝箱。

$q$ 个询问，每个询问先帮你解锁宝箱 $s$，问解锁 $[1,n]$ 需要用掉多少个金币。

$n,q \le 2\times10^5$

思考

考虑解锁的过程。暴力做法。
1. 因为区间一定是连续的，所以覆盖 $[1,n]$ 等价于覆盖 $1$ 和 $n$，通俗理解就是向左/右不断覆盖。
2. 单向的覆盖是经典问题：”最小区间覆盖“。这个问题有区间贪心的解法，也有图论建模的解法。
3. 这里我们考虑图论建模。将 $i$ 与 $[l_i,r_i]$ 连边权为 $1$ 的边，$dis_j$ 表示解锁 $j$ 点所需的最小金币数。解锁 $x$ 的最小金币数就是 $\min \limits_{x \in [l_j,r_j]} dis_j$。终点固定但起点不固定，因此我们建反图 $d1_i$ 表示从 $1$ 出发到 $i$ 的最小金币数，$dn_i$ 同理，跑多源 bfs 就可以求出这个。
4. 但是同时达到 $1$ 和 $n$ 点的最小代价并不简单等同于两个 $dis$ 相加，因为存在 “公用点” 或其他情况。
5. 仔细考虑扩展过程，将整个过程拆成向左/向右两个独立的部分。
  1. 猜测结论：最优扩展中，两个独立部分的某个前缀相同，且之后没有任何一个点相同。通俗地讲，只有一个分歧点。做过一个类似的树上路径问题，结论也是只有一个分歧点。
  2. 可以用调整法严格证明。如果两部分的选点集合在相同前缀之后还有一个相同点，那么一定有当前 $R<r_x \and l>l_x$（否则应该被归入公共前缀），选择它可以使两边同时扩展，所以此时将向左/向右部分替换成另一边是不劣的，因此 $x$ 一定是公共前缀。
6. 于是我们就可以枚举这个公共前缀 $x$，答案即为：$dis_x+d1_x+dn_x-1$，$dis_x$ 用 bfs 求，再遍历一遍取最小值，得到了 $O(\sum (r-l+1)+ nq)$ 做法。
考虑优化。
1. $d1_x+dn_x-1$ 是固定的，可视作初始距离，在此基础上跑多源桶排序 bfs（本质桶排序 dijkstra），即可求出从 $i$ 出发的最短距离。
2. 现在的瓶颈在于建图。这是线段树优化建图的经典应用了，单点与区间的连边，或区间与单点的连边都可以考虑线段树优化建图。具体就是将区间当作线段树上的节点，然后连边就好了。

旅行

题意

给你一个 $n$ 个点的内向基环树森林，$m$ 个询问，每个询问问从 $s$ 出发走 $t1^{t2}$ 步后，到了哪里。

$n \le 4\times 10^5$，$m \le 3\times 10^5$，$t1,t2 \le 10^9$

思考

如果数据范围不是那么离谱的话，可以直接倍增。这题显然要用到基环树的性质。
如果 $s$ 在环上，只需要看 $t1^{t2} \bmod len$ 的余数就可以了，这个可以快速幂做，时间复杂度 $O(\log t2)$。
如果 $s$ 不在环上，那先得先进环。预处理每个点到环的距离，以及到环的哪个点。
1. 若 $t1^{t2} \ge dis$，求 $t1^{t2}-dis \bmod len=(t2^{t2}\bmod len - dis \bmod len + len) \bmod len$。
2. 否则倍增即可。
用求 topo 的删边法处理出环上节点，多源 bfs。处理一个倍增函数。时间复杂度 $O(n \log n+m \log t2+m \log n)$。