首黑纪念。
2026-03-15 11:36:52
发布于：广东
这题怎么感觉要降。
https://www.luogu.com.cn/problem/P6272
难度：6.0 / Medium
题解
假设 ，计算时间复杂度等时所有 用 代替。
首先思考如何表示 。
我们可以动态开点，每个数 分别指向 的下标，就可以递归表示 。
查询显然用线段树维护。
现在考虑如何比较 的大小。
考虑维护一个平衡树，表示出现的数的排名。
现在插入一个数。由于每次插入会改变后面所有 的排名，所以可能改变所有 中 的排名，所以不能重新标号，每次比较只能通过动态查询排名得出。一次插入会比较 个数，每次都要查询 次排名，一次查询是 的，所以插入一个数是 的。
而更新线段树也需要比较 次，所以查询也是 的。
总时间复杂度 ，但只有 1s 时间，常数大过不了。
发现瓶颈在于必须动态查询排名才能比较大小。考虑用一种更快的方法比较。
我们可以用实数代替整数排名。这样，只需要将排名设为两数的中间值，其它排名都不用变。
但这样如果每次修改的数都比原来的小，最后的实数就是 ，显然任何浮点数类型都存储不下。
注意到按照实数加入顺序建树，建出来的是一颗与原树（如果不进行平衡操作）完全一样的 BST。所以考虑在原树做平衡操作时，同时改变实数排名降低精度。显然最简单的办法就是暴力重构。
那替罪羊树可不可以做呢？
正常情况下，精度不超过 即可。当然，这里由于不需要判断 eps（因为完全相等的浮点数进行相同的运算结果一定完全相等），所以精度要求还可以更高。不过这里还是看做 。
替罪羊树的最大深度是 。
所以此时最高精度为 。
当 取 时，精度约为 ，完全够用。
时间复杂度 。
record：https://www.luogu.com.cn/record/267342439
有帮助，赞一个