我曾经会写平衡树

· · 生活·游记

哇 T1 好难，我一分都不会。

对于这种简单题，我们显然是可以用平衡树的，对于 10^5 的数据范围我并不知道能不能过，所以我觉得应该要写 LCT。我不会。

所以我觉得 T1 不应该是平衡树，但是我觉得就是平衡树。

于是我开始尝试手搓 Splay。但是一想到数据范围是 10^5 我就觉得要写 LCT，而我并不会 LCT，所以我认为这就是一个非常困难的题目。因为我不会写。

所以我决定开始想更快的平衡树做法是什么，但是我不知道 Splay 应该怎么写，也不知道 LCT 应该怎么做。

因此我开始思考性质 B，显然是带权类似于二分图的匹配。因此很不难想到平衡树，但是我并不会平衡树。

于是我开始尝试手搓 Splay。但是一想到数据范围是 10^5 我就觉得要写 LCT，而我并不会 LCT，所以我认为这就是一个非常困难的题目。因为我不会写。

所以我决定开始想更快的平衡树做法是什么，但是我不知道 Splay 应该怎么写，也不知道 LCT 应该怎么做。

因此我开始思考性质 A，显然是很简单的，我们可以使用可持久化平衡树来解决。

不过我并不知道可持久化平衡树应该怎么写，所以我觉得这道题非常困难。

于是我开始尝试手搓可持久化 Splay。但是一想到数据范围是 10^5 我就觉得要写 LCT，而我并不会 LCT，所以我认为这就是一个非常困难的题目。因为我不会写。

所以我决定开始想更快的可持久化做法是什么，但是我不知道可持久化应该怎么写，也不知道 LCT 应该怎么做。

我已经破防了，我没有任何希望了。这是我第一次在 NOIP 中被 T1 创飞 30min 而没有开始写代码。

于是我决定先开始写代码，我开始寻找平衡树的写法。

但是一想到数据范围是 10^5 我就觉得要写 LCT，而我并不会 LCT，所以我认为这就是一个非常困难的题目。因为我不会写。

不过我现在才知道我应该写的是可持久化平衡树，我没记错的话可持久化的复杂度和树高有关系。所以我并不是很会这道题目。

因此我开始思考假算应该怎么写。

我开始考虑 B 性质。

我发现这是一道很简单的形式，因为我们要把他们分成两组然后求权值和的最大值。这很显然可以使用平衡树来做。不对应该是可持久化。

不过我并不知道可持久化应该怎么写，所以我觉得这道题非常困难。

于是我开始尝试手搓可持久化。但是一想到数据范围是 10^5 我就觉得要写 LCT，而我并不会 LCT，所以我认为这就是一个非常困难的题目。因为我不会写。

所以我决定开始想更快的可持久化做法是什么，但是我不知道可持久化应该怎么写，也不知道 LCT 应该怎么做。

因此我觉得我不应该思考可持久化和 Tree 相关的做法。

我认为贪心是很没有前途的东西，于是我决定从 dp 开始找性质。

我发现这个 n^3 的 dp 非常适合用可持久化平衡树来做。不对！我不应该思考可持久化应该怎么做！我不会可持久化！

于是我考虑转化为树上启发式合并模型，但是我决定在推到模型之前检验一下自己会不会平衡树。

对于 10^5 的数据范围我并不知道能不能过，所以我觉得应该要写 LCT。我不会。

所以我觉得 T1 不应该是平衡树，但是我觉得就是平衡树。

于是我开始尝试手搓 Splay。但是一想到数据范围是 10^5 我就觉得要写 LCT，而我并不会 LCT，所以我认为这就是一个非常困难的题目。因为我不会写。

所以我决定开始想更快的平衡树做法是什么，但是我不知道 Splay 应该怎么写，也不知道 LCT 应该怎么做。

因此我开始思考性质 B，显然是带权类似于二分图的匹配。因此很不难想到平衡树，但是我并不会平衡树。

我发现我已经有 60 分钟在思考平衡树了。这对身体很不好，我开始克制自己思考平衡树。

于是我考虑贪心。但是作为一个提高组选手，我并不会贪心，甚至在考前复习了很多次的 积木大赛 也都快忘记怎么写了。

于是我考虑线段树优化 dp。我发现可以用平衡树来做，于是我发现我正在思考平衡树。所以我应该上厕所冷静一下。

于是打算写一个贪心，无论怎样都要强迫自己写出一个贪心算法出来。

于是我终于写出来了一个贪心算法，这是一个反悔贪心，但是只能通过 B 性质，于是我决定思考平衡树。

我不打算继续思考了，于是我决定用我仅存的理智把我的贪心算法写完善。

于是我拍子过了，但是我仍然发现我的这个东西是可以被 Hack 的。不过我不可能在 T1 做超过 1.5 小时，所以我决定跳过 T1。

对于 T2 找到一个联通的方式我可以想到模拟退火，想到模拟退火我就可以用随机化来做。

所以我觉得 T2 不应该是平衡树，但是我觉得就是平衡树。

于是我开始尝试手搓 Splay。但是一想到数据范围是 10^6 我就觉得要写 LCT，而我并不会 LCT，所以我认为这就是一个非常困难的题目。因为我不会写。

所以我决定开始想更快的平衡树做法是什么，但是我不知道 Splay 应该怎么写，也不知道 LCT 应该怎么做。

因此我开始思考性质。因此很不难想到平衡树，但是我并不会平衡树。

于是我开始尝试手搓 Splay。但是一想到数据范围是 10^6 我就觉得要写 LCT，而我并不会 LCT，所以我认为这就是一个非常困难的题目。因为我不会写。

所以我决定开始想更快的平衡树做法是什么，但是我不知道 Splay 应该怎么写，也不知道 LCT 应该怎么做。

我意识到这道题不能用平衡树来做，因此我得考虑别的算法。

我想到了最小生成树，于是我卡常过了。

我怀着激动的心情打开 T3，我感到非常悲伤，因为我发现这道题几乎不能使用平衡树来做。

难道平衡树就不能做了吗？我认为，在思考这个问题之前，我应该思考我会不会写平衡树。

于是我开始尝试手搓 Splay。但是一想到数据范围是 2\times 10^6 我就觉得要写 LCT，而我并不会 LCT，所以我认为这就是一个非常困难的题目。因为我不会写。

所以我决定开始想更快的平衡树做法是什么，但是我不知道 Splay 应该怎么写，也不知道 LCT 应该怎么做。

于是我开始尝试手搓 Splay。但是一想到数据范围是 2\times 10^6 我就觉得要写 LCT，而我并不会 LCT，所以我认为这就是一个非常困难的题目。因为我不会写。

所以我决定开始想更快的平衡树做法是什么，但是我不知道 Splay 应该怎么写，也不知道 LCT 应该怎么做。

因此我开始思考性质，显然是很简单的，我们可以使用可持久化平衡树来解决。

不过我并不知道可持久化应该怎么写，所以我觉得这道题非常困难。

于是我开始尝试手搓可持久化。但是一想到数据范围是 2\times 10^6 我就觉得要写 LCT，而我并不会 LCT，所以我认为这就是一个非常困难的题目。因为我不会写。

所以我决定开始想更快的可持久化做法是什么，但是我不知道可持久化应该怎么写，也不知道 LCT 应该怎么做。

我已经破防了，我没有任何希望了。现在比赛已经进行到 2.5 小时了，我仍然只有 200 分不到。

于是我决定先开始写代码，我开始寻找平衡树的写法。

但是一想到数据范围是 2\times10^6 我就觉得要写 LCT，而我并不会 LCT，所以我认为这就是一个非常困难的题目。因为我不会写。

不过我现在才知道我应该写的是可持久化平衡树，我没记错的话可持久化的复杂度和树高有关系。所以我并不是很会这道题目。

因此我开始思考假算应该怎么写。

但是此时我想到我的 T1 可能也需要可持久化才能得到正确的做法，于是我决定思考可持久化怎么做，毕竟可持久化可以代替平衡树，虽然可能会 TLE，但是这是我的希望。

不过我并不知道可持久化应该怎么写，所以我觉得这道题非常困难。

于是我开始尝试手搓可持久化。但是一想到数据范围是 2\times10^6 我就觉得要写 LCT，而我并不会 LCT，所以我认为这就是一个非常困难的题目。因为我不会写。

所以我决定开始想更快的可持久化做法是什么，但是我不知道可持久化应该怎么写，也不知道 LCT 应该怎么做。

因此我觉得我不应该思考可持久化和 Tree 相关的做法。

我认为平衡树是很没有前途的东西，于是我决定从字典树开始找性质。

我发现这个模型非常适合用 Splay 来做。不对！我不应该思考可持久化应该怎么做！我不会可持久化！

于是我考虑转化为树剖模型，但是我决定在推到模型之前检验一下自己会不会平衡树。

对于 2\times10^6 的数据范围我并不知道能不能过，所以我觉得应该要写 LCT。我不会。

所以我觉得 T3 不应该是平衡树，但是我觉得就是平衡树。

于是我开始尝试手搓 Splay。但是一想到数据范围是 2\times10^6 我就觉得要写 LCT，而我并不会 LCT，所以我认为这就是一个非常困难的题目。因为我不会写。

所以我决定开始想更快的平衡树做法是什么，但是我不知道 Splay 应该怎么写，也不知道 LCT 应该怎么做。

因此我开始思考哈希应该怎么做。

我发现我可以枚举每一种的方案然后判断即可统计答案，随后我突然意识到枚举每一个方案的时间复杂度是多项式复杂度的！我真是个天才，我居然会了 poly 时间复杂度做法！

但是我想到平衡树也是 poly 时间复杂度的，因此我开始思考平衡树应该怎么做。

我还是不会平衡树。

我真的不会平衡树吗？

我真的不会平衡树。

我学了两年还不会一个平衡树吗？

我真的不会平衡树。

此时，我才意识到，我在这一年内几乎就没有任何的进步，在模拟赛中不会的题永远不会，而这些不会的题目，正是阻断着我进步的东西。

我开始思考我在这整整一年中我到底进步了什么，我到底学会了什么？是平衡树吗？不，我没有学会，因为我思考了很久的平衡树我并不会。

那我为什么学了整整一年还是不会平衡树呢？我是否真正的在这一年中没有学会任何东西？每天随随便便地找一些题目来做，我就会平衡树了吗？我就真正的在我的 OI 之路上取得进步了吗？

我曾经特别喜欢在闲暇时间打 duel，直到以后要我才明白，这用 duel 的方式来提升自己的实力，简直就和我学习平衡树一样低效率！

我真正收获了什么吗？我取得了更好的进步吗？我每天都沉浸在自己喜欢做的数位 DP 题目中，每天做数位 DP 题目做到发癫，但是考试真的会考吗？即使会考又如何呢？

我根本就没有一种好的学习方法来学习 OI！我整整荒废了整整一年的时间！我什么都没有得到！

想到这里，我的眼眶慢慢地被晶莹的眼泪覆盖。我不禁开始后悔，可是世界上哪里有什么后悔药啊。

我想 Splay 的思想也是类似的，因为 Splay 就是通过 rotate 来起到“反悔”的一个作用。可是这世上哪里有什么 rotate。

:::info[创作说明] 本文使用 Gemini 创作，经过了少许人工微调。 :::