关于替罪羊树实现的一点疑问

先放下我的代码

整体上没大问题，但注意看lift函数的这段：

因为在朴素的二叉搜索树中，若后插入的数与前数相等，那么后插的数会放在前数的右子树上

但是在替罪羊的lift操作中如不特判，一个数的左子树上会出现与它相等的数，这与朴素的二叉搜索数相悖，所以我们加了while循环特判，将提起来的根左挪到了upper_bound(相等数的前数）上

但这样又出现了新的问题，那就是如果一直插入同样的数，根就会一直左挪，最后会退化成一条链，单次查询时间复杂度从O(log N)退化到O(N)，会TLE，那又该怎么办

我目前猜测只能把while循环删了，然后重写getrank等函数的部分会产生错误的代码，但似乎很麻烦，我打算在学完主席树和莫队后再来搞这个，就当是开了个新坑吧

试问诸位Dalao是怎么解决这个问题的，MnZn跪求

upd on 2023/1/27

有想法了，考虑二叉查找树的每个节点存一对pair，first存val，second存num，如插入相等val(无论是否连续）就将num++，size存实际节点数，fact类似，删除时只有num降到0时才将其exist打上false，getnum和getrank的修改可以参考ODT的区间幂次和操作

应该可行，有时间就码