2023 6月记录

6.6

[CF1830E] Bully Sort

很离谱的结论题！
这个操作很奇怪，但是它有一个重要的性质：一个数永远只会向一个方向移动。考虑这个操作的过程，每次其实是将 \(p_i \neq i\) 的最大的 \(i\) 归位，所以如果一个数向右移，它以后就不会向左移。而一个数如果向右移，那么它一定是一个后缀 \(min\)，而又有 \(sufmin_i\le i\)，所以每个 \(p_i\) 往左不会移到 \(i\) 左侧，所以它以后也不会往右移。
有了这个结论我们可以刻画一个 “距离” \(s_1=\sum |p_i-i|\)，我们每次操作交换一个 \((x,y)\)，它们都是向距离减少的方向移动，于是 \(s_1\) 减少 \(2(y-x)\)。
我们再抓出一个关键的值 “逆序对数” \(s_2\)，操作 \((x,y)\)，根据操作的定义对于 \(x<i<y\)，一定有 \(p_x>p_i>p_y\)，再加上 \((x,y)\) 也是逆序对。所以这一次操作将会减少 \(2(x-y-1)+1\)。
一个有序的排列的 \(s_1,s_2\) 都为 \(0\)，而每次操作 \(s_1\) 都比 \(s_2\) 都多减少 \(1\)。于是操作次数就为 \(s_1-s_2\)。

\(s_1\) 的维护是简单的，\(s_2\) 的维护就见仁见智，cdq 分治跑三维数点好像是比较快的选择。

[模拟赛20230606] 差

不难发现我们其实只关心差分数组，于是可以出一个 \(dp\)，\(f_{i,j}\) 表示满足 \(b_1 \sim b_{i-1}\) 时 \(|a_{i+1}-a_i|\) 能否为 \(j\)。
转移的时候讨论一下，可以列出以下几条转移：

1. \(f_{i,j}(0\le j \le b_i) \rightarrow f_{i+1,b_i}\)
2. \(f_{i,b_i} \rightarrow f_{i+1,j}(0\le j \le b_i)\)
3. \(f_{i,j}(0\le j \le b_i) \rightarrow f_{i+1,b_i-j}\)

然后考虑打印答案，我们可以直接得出所有差分的绝对值，考虑转移的意义，转移 3 是两个差分加起来为 \(b_i\)，转移 1,2 是差分的较大值为 \(b_i\)。所以如果是转移 3，那么符号相等，转移 1,2 则相反。
构造出差分就可构造出原序列了！

在此基础上优化，发现转移 1,2 都比较简单，而转移 3 其实就是把整个状态翻转再平移，这是好记录的。于是我们每次的操作就是把超出 \([0,b_i]\) 的赋值为 \(0\)，一转移是将边界上的一项变为 \(1\)，二转移是将 \([0,b_i]\) 整个区间变为 \(1\)。

发现每次操作都是在别街上修改，于是我们使用链表维护 dp 值为 \(1\) 的连续段。然后要求方案，就要记录每个连续段在什么时候从哪个连续段的那个位置转移过来。

[模拟赛20230606] 贼

从 SAM 的角度考虑，可以把式子写成以下形式：

建出反串的 parent 树，lcp 就是 lca 的 len。

如果只求 \(\sum lcp(l,i)\) 都比较麻烦，结果还要带个 min！很难过。

之前有道求区间 border 的题和这题有些类似，当时那到题处理 lcp 是用树剖，把 \(l\) 到根剖成重链，对于每个重链，查询与 \(l\) 的 lca 在这条链上的所有答案。

但是每个重链上的点需要按照深度顺序逐渐加入，经过分析，每次加完点以后发现要做个二维数点，总的就是三维数点，再加上树剖，总的就是三个 log！

但是回想当年那到题，还有一个点分治的做法，在那到题上略显复杂，但是在这道题上十分的合适。

具体的，对于当前分治的一个连通块，考虑所有经过分治中心 \(rt\) 的 \((l,i)\) 的贡献。这个时候 \(lca(l,i)\) 只与 \(l\) 或者 \(i\) 有关。

找到当前连通块内深度最小的点 \(mn\)，我们对于 \(i\) 是否与 \(mn\) 在 \(rt\) 的同一子树分类讨论。

1. 如果 \(i\) 和 \(mn\) 不在同一子树内，那么 lca 只与 l 有关，即对于每个 l 找出它到分治中心深度最小的点。于是已知 lcp 的长度，跑一个二维数点即可求出这个的答案。
2. 如果 \(i\) 和 \(mn\) 在同一子树内，那么 lca 只与 i 有关，那么我们对于每个查询的 \(l\) 同样可以做二维数点。

然后要把 \(l,i\) 都在同一子树内的情况容斥掉。

代码有些细节，需要注意一下。

[模拟赛20230606] 点

这个题更是比较离谱，但是其实如果想到对 \(d\) 大小分治，那么还是不太难。

本题可以转化为必须在 \(x,x+2d\) 选一个，这样比较好看。

对于 \(d\) 比较小的情况可以状压，我们可以记录每一个位置是否被包含在一个连续段内，于是此时一个 \(01\) 贡献 \(A\)，一个 \(11\) 贡献 \(B\)。状压记录下最后 2d 个位置的状态，即可进行转移，复杂度 \(O(n2^{2d})\)，发现在 \(d\) 很小的时候跑得过。

于是考虑当 \(d\) 很大怎么办，发现每一个位置的状态 \(p\) 其实只与 \(p-2d\) 的状态有关，于是我们可以换一个 dp 顺序。我们把所有位置按照模 \(2d\) 分类，一类一类依次确定，这下我们记录了上一项是否被选，于是就知道当前是否必须选，然后计算贡献就需要记录上衣类的所有状态，可以类似轮廓线dp一样维护。除此以外，还要考虑第一类和最后一类的贡献，就只能先枚举第一类的状态再开始 dp，复杂度 \(O(n 2^{2(n/d)})\)。

平衡一下，当 \(d \le 8\) 时跑做法一，当 \(d> 8\) 时跑做法二。

对于这种 \(d\) 固定的题目，有一种经典的转化是将一维的序列排成二维的矩阵，将 \(2d\) 个位置排成一行，然后这两种做法就相当于是按照行的顺序还是列的顺序确定，然后相当于是从这两个方向做轮廓线dp。

人造情感

这位比较重量级，首先暴力其实就不好打。不发发现 \(f(u,v)\) 就是 \(W(s)\) 减去 钦定 \((u,v)\) 路径上的点都不被选的 \(W\)，而钦定 \((u,v)\) 路径上的点都不被选，剩下的部分就被分为了若干个连通块，其中有一个是 \((u,v)\) lca 的为子树，其它的事 \((u,v)\) 路径上的点的子树。于是我们要求的就是 所有子树的 \(W\) 和所有外子树的 \(W\)。

首先考虑求全局的 \(W\)。令 \(f_x\) 表示 \(x\) 子树内的答案，然后 \(f'_x=f_x-\sum _{y \in son(x)} f_y\)。一下默认 \(y\) 为 \(x\) 的儿子，考虑转移，首先 \(f_x\) 可以为 \(\sum f_y\)，即 \(f’_x\) 可以为 \(0\)。然后枚举 lca 为 \(x\) 的一条路径 \((u,v)\) 那么我们可以钦定这条路径被选，那么就会钦定这条路径上的所有点都不被选，那么就会减少 \(\sum _{p\in (u,v)} f'_p\) 的收益，于是 \(f'_p=max_{(u,v)} w_{(u,v)} -\sum _{p \in (u,v)} f'_p\) ，然后把这个值于 \(0\) 取max。我们可以用树状数组维护单点改链查的信息，于是我们可以一遍 \(O(n \log n)\) 地求出每个子树的 \(f\)。

但是外子树就很烦。如果直接换根 dp 的话，那么每一条路径在每个点都会被枚举到，复杂度就寄了。但是我们可以树剖，每次只考虑往中儿子的，往轻儿子的就可以在此基础上用堆维护，细节很多，懒得写了，最后复杂度 \(O(n \log n)\)。

「SNOI2020」水池

考虑这道题的操作本质上会带来什么影响。

1. 操作一实际上就是找出左右最近的高度大于 \(h\) 的挡板，然后把这一段区间赋值为 \(h\)。
2. 操作二相当于操作一的逆操作，还是找出这么一段区间，然后把每个位置的值赋值为它到 \(x\) 之间挡板的最高高度。

一操作可以用主席树标记永久化维护，二操作比较麻烦，头铁的话，硬上用标记维护是可以的，但是这就非常的难写，而且必须 pushdown，我当时卡了一个小时空间，终于卡过了。

但是实际上，这个题有更简单的做法：我们只需要记录一下每个位置的最终高度是由哪个操作决定的，如果是操作二，我们抽查一下这一段区间挡板高度的最大值即可，这样就只需要区间打 tag 就行了，好写空间也小。

「LibreOJ β Round #7」网格图

可以把整张图横向和竖向地划分成连续段，一个连续段之间的可以随便走，而如果一个横向的和一个纵向的相交，就可以一步走过去，于是我们可以建出图，主席树优化建图即可。

「2021 集训队互测」蜘蛛爬树

很明显一次查询 \((u,v,t)\) 我们会从 \(u\) 走到某个中转点 \(x\) 再走到 \(v\)，这样的距离就是 \(dis_{(u,x)}+a_x \times t + dis_{{x,v}}\)。

于是可以写出 \(O(nq)\) 的暴力。观察到有一个 \(a_x \times t\) 的交叉项，于是肯定要用凸包，一种想法是枚举 \(x\) 在 \((u,v)\) 路径上哪个点的子树之中，然后我们在假如哪个点是 \(y\)，那么距离就是 \(dis_{(u,v)}+2dis_{(y,x)}+a_x \times t\)，于是我们可以对 \((a_x,dis_{y,x})\) 建立坐标系求凸包。

但是 \((u,v)\) 路径上的点实在是太多了，复杂度太高，在此基础上考虑优化。要缩短路径的长度，考虑抓出点分树，点分树的其中一个优美的性质是 \(dis_{(u,v)}=dis_{(u,lca(u,v))}+dis_{(v,lca(u,v))}\)，其中 \(lca(u,v)\) 是 \(u,v\) 在点分树上的 \(lca\)。我们枚举 \(x\) 和 \((u,v)\) 这条路径的 \(lca\) ，那么此时 \(lca(u,x),lca(v,x)\) 都确定了，这两个点是一对祖先后代，这样的点对只有 \(O(nlog)\) 个，我们对于每个点对求出凸包然后计算答案，总复杂度就是 \(O(n\log^2)\)。