DS 加训记录

波特给的题单。传送门。

CF526F Pudding Monsters (Easy)

转化成有多少子区间 $[l, r]$ 满足 $\max - \min = r - l$。

扫描线，考虑每一个 $r$ 的贡献。用两个单调栈维护 $\max, \min$，线段树区间赋值，查询最小值个数。

CF464E The Classic Problem (Easy-Medium)

实际上只需要一个数据结构来实现 01 串的加法和比较大小。

由于边权都是 $2^x$ 的形式，考虑线段树维护单点修改。可以 path copy 后把一段区间的 $1$ 改成 $0$，再把前面的一个 $0$ 改成 $1$（进位）。

然后是比较两个 01 串的大小关系，维护哈希值，线段树上二分 LCP 即可。

Dijkstra 实现的最短路可以做到 $O(m \log m \log X)$。

CF1446D2 Frequency Problem (Hard Version) (Medium-Hard*)

套区间众数的根号做法显然能过。

考虑二分答案，然后双指针。但你发现区间众数不能带删。但是猫树分治一下就行了。

全假了。怎么不会 shaber 破紫啊？

上面的做法问题出在众数信息是不好合并的。

一个没想到的结论是，全局众数 $M$ 一定是答案子区间的众数。证明考虑若 $M$ 不是当前子区间众数，一定可以扩展区间让 $M$ 成为子区间众数，这样答案更优。

然后可以 $O(V)$ 枚举答案子区间另一个众数，$O(n)$ 扫一遍判断是否存在合法子区间让二者出现次数相同。

套路地想到根号分治：出现次数大于 $\sqrt{n}$ 的数不会超过 $O(\sqrt{n})$ 种，可以套刚才的做法做到 $O(n\sqrt{n})$；而对于出现次数不超过 $\sqrt{n}$ 的数，直接枚举答案子区间的众数出现次数，然后双指针判是否存在某个子区间能取到这个次数，也是 $O(\sqrt{n})$。

存在 $O(n\log^2 n)$ 甚至 $O(n\log n)$ 甚至 $O(n)$ 做法。咕咕咕。

CF997E Good Subsegments (Medium)

把 Pudding Monsters 和 NOIP2022 比赛 这俩题的做法拼起来就行了。

具体地，线段树维护区间最小值及个数。然后要区间加减，查询最小值个数历史和。要维护加法和贡献两个标记。

注意要先下传加法标记再判断能否产生贡献。这个东西很难描述成双半群的 $\mathcal{D} \times \mathcal{M}$，要在下传标记的时候单独判。

提交记录。

CF319E Ping-Pong (Hard*)

好题。比较遗憾的是想了 $3\log$ 状物之后就摆烂看了题解，导致没有思维过程。

首先可以转成图连通性，相交连双向边，包含连单向边。双向边用并查集维护，单向边直接在查询时判一下包含。

对于线段 $[l, r]$，与先前所有严格包含 $l$ 或 $r$ 的线段连边。由于保证加入线段的长度单调递增，不难证明这样的边都是双向边。

同时，可以发现双向边构成的连通块也一定是一条线段。合并的时候求一下线段并，即可维护出连通块线段。

然后把所有连通块线段拆成 $\log$ 条插入线段树，每次连边只需要线段树上查返祖链，再把合并后的连通块线段插入回线段树。

连边操作和插入线段树的复杂度都是 $O(n\log n)$。

CF1163F Indecisive Taxi Fee (TODO)

CF436F Banners (Medium-Hard)

前面的贡献是容易的。转化成前缀加公差为 $1$ 的等差数列，全局查询最大值。

看起来不太容易做到 $\log$，考虑分块。整块打加法标记，查询相当于求 $\max(a_i + ik)$。经典维护上凸壳，用斜率为 $-k$ 的斜线扫凸壳即可。由于 $k$ 不降，可以单调队列。

至于散块，暴力下放标记，然后重构即可。$O(n\sqrt{n})$。

CF773E Blog Post Rating (x)

不知道题意在说什么。看了眼题解好像值域线段树随便做做，那扔了。

CF765F Souvenirs (Hard*)

上个赛季胡策的题。

CF176E Archaeology (Easy-)

导出子树大小是按 dfn 排序计算两两距离再除以二。

用 set 维护，$O(1)$ 查询 LCA 就可以 $O(n\log n)$。

CF896E Welcome home, Chtholly (Hard*)

第二分块弱化版。

CF679E Bear and Bad Powers of 42 (Medium-Hard*)

写写写，挂挂挂，2h 后发现做法假了。唉唉。

首先发现 $42$ 的幂非常少。如果没有 2 操作，可以维护每个数到下一个 $42$ 的幂的差值，如果出现负数则单点修改。摊还分析一下是对的。

如果有 2 操作，由于区间推平会重置势能，刚才的做法复杂度是错的。

但区间推平又带来了颜色段均摊的性质。因此考虑把每个值相同的连续段当成同一个数，套用刚才的做法，这样就是对的了。

设一个区间的势能为，对于区间内每个值为 $v$ 的值相同连续段，大于 $v$ 的 $42$ 的幂的个数之和。

每次 2, 3 操作均会增加 $O(\log_{42} V)$ 的势能，算上线段树 $O(\log n)$ 的代价，总复杂度 $O((n + q)\log n\log_{42} V)$。

代码实现上参考了 Alex_Wei，使用类似标记永久化的方式可以方便地维护连续段。

CF571D Campus (Medium)

4 操作相当于给集合内的元素打时间戳，5 操作只需查询当前点的最后一个时间戳之后的 3 操作贡献。

离线建出两棵合并树。3 操作转化成第一棵树上子树加，4 操作转化成第二棵树上更新子树时间戳。子树加查单点再转化成单点加查返祖链。于是只需在第一棵树上建主席树，查询时先在第二棵树上查时间戳，再到第一棵树上查返祖链上某个时间段的贡献。

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

CF407E k-d-sequence (Medium)

首先把 $a_i$ 按照模 $d$ 分类，每次考虑一个极长的 $a_i \bmod d$ 相同连续段。

然后我们现在只关心 $a_i / d$ 的值，转化成求最长子区间加入至多 $k$ 个数后公差为 $1$。

一个合法子区间有两个限制：子区间中的 $a_i / d$ 两两不同，以及 $(\max - \min) - (r - l) \le k$。

考虑固定 $r$，前者可以记录值相同的前驱 $pre_i$，合法的 $l \ge \max(pre[1\dots r])$；后者写成 $\max - \min + l \le k + r$，单调栈维护 $\max, \min$​，再转化成求小于某个值的最小的下标。线段树二分。

CF700D Huffman Coding on Segment (Medium)

下面认为 $n, V$ 同阶。

莫队，然后考虑已知 $cnt$ 数组怎么计算答案。

经典根号分治，开桶记录每个 $cnt$ 的出现次数，小于 $B$ 的部分可以 $O(B)$ 算，大于 $B$ 的部分可以直接优先队列做到 $O\left((n / B)\log (n / B)\right)$。$B$ 取 $\sqrt{n\log n}$ 最优。

注意这个根号分治的阈值和莫队块长不一样。不过写成一样的也能过。

CF1515H Phoenix and Bits (Hard)

建一棵线段树维护类似 01-Trie 的结构。按位与可以写成按位或和按位异或的复合，因此只需要支持如下操作：

• 线段树分裂，合并。
• 对于某层的所有结点，翻转它们的左右儿子。
• 对于某层的所有结点，把它们的左子树合并到右子树上。
• 查询区间和。

暴力的实现可以打 tag，然后平衡树合并，做到 $\mathrm{polylog}$。

考虑一些优化。记录每个结点对应的子树中，哪些层只有左儿子没有右儿子，哪些层只有右儿子没有左儿子。

然后能剪枝的地方都剪掉。可以证复杂度是 $O(n\log^2 n)$，但是为什么？不知道。咕。

实现上和线段树分裂 / 合并差不多。参考了 Verdandi 的代码。

---

短时间内不想做 ds 了。开摆。