先放下我的代碼

整體上沒大問題，但注意看lift函數(shù)的這段：

因為在樸素的二叉搜索樹中，若后插入的數(shù)與前數(shù)相等，那么后插的數(shù)會放在前數(shù)的右子樹上

但是在替罪羊的lift操作中如不特判，一個數(shù)的左子樹上會出現(xiàn)與它相等的數(shù)，這與樸素的二叉搜索數(shù)相悖，所以我們加了while循環(huán)特判，將提起來的根左挪到了upper_bound(相等數(shù)的前數(shù)）上

但這樣又出現(xiàn)了新的問題，那就是如果一直插入同樣的數(shù)，根就會一直左挪，最后會退化成一條鏈，單次查詢時間復雜度從O(log N)退化到O(N)，會TLE，那又該怎么辦

我目前猜測只能把while循環(huán)刪了，然后重寫getrank等函數(shù)的部分會產(chǎn)生錯誤的代碼，但似乎很麻煩，我打算在學完主席樹和莫隊后再來搞這個，就當是開了個新坑吧

試問諸位Dalao是怎么解決這個問題的，MnZn跪求

upd on 2023/1/27

有想法了，考慮二叉查找樹的每個節(jié)點存一對pair，first存val，second存num，如插入相等val(無論是否連續(xù)）就將num++，size存實際節(jié)點數(shù)，fact類似，刪除時只有num降到0時才將其exist打上false，getnum和getrank的修改可以參考ODT的區(qū)間冪次和操作

應該可行，有時間就碼