这题怎么感觉要降。
https://www.luogu.com.cn/problem/P6272
难度：6.0 / Medium
题解
假设 q=n=5×105q=n=5\times 10^5q=n=5×105，计算时间复杂度等时所有 qqq 用 nnn 代替。
首先思考如何表示 AiA_iAi 。
我们可以动态开点，每个数 (x,y)(x,y)(x,y) 分别指向 x,yx,yx,y 的下标，就可以递归表示 AiA_iAi 。
查询显然用线段树维护。
现在考虑如何比较 AiA_iAi 的大小。
考虑维护一个平衡树，表示出现的数的排名。
现在插入一个数。由于每次插入会改变后面所有 (x,y)(x,y)(x,y) 的排名，所以可能改变所有 (x,y)(x,y)(x,y) 中 x,yx,yx,y 的排名，所以不能重新标号，每次比较只能通过动态查询排名得出。一次插入会比较 O(logn)O(\log n)O(logn) 个数，每次都要查询 222 次排名，一次查询是 O(logn)O(\log n)O(logn) 的，所以插入一个数是 O(log2n)O(\log^2 n)O(log2n) 的。
而更新线段树也需要比较 O(logn)O(\log n)O(logn) 次，所以查询也是 O(log2n)O(\log^2 n)O(log2n) 的。
总时间复杂度 O(nlog2n)O(n\log^2 n)O(nlog2n)，但只有 1s 时间，常数大过不了。
发现瓶颈在于必须动态查询排名才能比较大小。考虑用一种更快的方法比较。
我们可以用实数代替整数排名。这样，只需要将排名设为两数的中间值，其它排名都不用变。
但这样如果每次修改的数都比原来的小，最后的实数就是 2−n2^{-n}2−n，显然任何浮点数类型都存储不下。
注意到按照实数加入顺序建树，建出来的是一颗与原树（如果不进行平衡操作）完全一样的 BST。所以考虑在原树做平衡操作时，同时改变实数排名降低精度。显然最简单的办法就是暴力重构。
那替罪羊树可不可以做呢？
正常情况下，精度不超过 10−1010^{-10}10−10 即可。当然，这里由于不需要判断 eps（因为完全相等的浮点数进行相同的运算结果一定完全相等），所以精度要求还可以更高。不过这里还是看做 10−1010^{-10}10−10。
替罪羊树的最大深度是 log1αn\log_{\frac{1}{\alpha}} nlogα1 n。
所以此时最高精度为 2−log1αn=n−1log21α2^{-\log_{\frac{1}{\alpha}} n}=n^{-\frac{1}{\log_2\frac{1}{\alpha}}}2−logα1 n=n−log2 α1 1 。
当 α\alphaα 取 0.6597530.6597530.659753 时，精度约为 (2n)−1.6667≈10−10(2n)^{-1.6667}\approx 10^{-10}(2n)−1.6667≈10−10，完全够用。
时间复杂度 O(nlogn)O(n\log n)O(nlogn)。
record：https://www.luogu.com.cn/record/267342439
