As noted in https://mirror.codeforces.com/blog/entry/108457#comment-1182660, https://atcoder.jp/contests/abc276/editorial/5188 for https://atcoder.jp/contests/abc276/tasks/abc276_f gave me the desire for an implementation that supports the following (all in $$$\log n$$$ time of course).
- Insert a number to list (which can contain duplicates)
- Delete a number from that list
- Query for sum of elements in list strictly greater than x
- Query for number of elements in list strictly greater than x
(1), (2), (4) are supported by policy based data structures with the caveat that it might not actually work for multiset. At least on my local machine, it did not with -D_GLIBCXX_DEBUG flag. I could not easily find anything online that supports (3) in addition to duplicates (in the process, I also searched for treap and splay tree implementations).
By modifying existing AVL Tree code in GitHub that already supports (1), (2), (4) per https://github.com/guoyiz23/AVL-Tree/commit/1956db850abd0401b8734e7534ca9979b6f85568 , (3) is now supported. It was tested via diffing outputs on randomly generated cases with slow version, as well as via https://atcoder.jp/contests/abc276/submissions/56670045 , which ACs the problem linked above.
I hope that some people will find this useful.
