### noobinho's blog

By noobinho, history, 5 years ago, I'm trying to solve the problem: http://acm.timus.ru/problem.aspx?space=1&num=1439. It consists basically in m (1 <= m <= 10^5) queries in an ordered set which can be of two types: 1) eliminate an element of the ordered set (the number of elements eliminated is at most 10^4); 2) find the kth element of the ordered set. The ordered set can have at most n elements (1 <= n <= 10^9).The elements are {1,2,...,n} at the beginning. I tryed to code a dynamic segment tree to solve in O(m*logn) of time, as follows:https://ideone.com/e.js/jLFIMv. However, it gave MLE. So, I want to know what I can do to improve the memory used. Thanks in advance Comments (8)
| Write comment?
 » Why do you indent your code so weirdly?
 » 5 years ago, # | ← Rev. 2 →   At the current time your node is 32 bytes size. You can use indexes in array / vector against pointers because one pointer is 8 bytes, but one index is 4 bytes (32-8=24, 66% memory). You exactly need to keep integers l and r in node? Maybe you can put l and r as parameters in functions in "set" and "get" queries?
•  » » With the contraints that were given (1 <= n <= 10^9) I think it's infeasible to use indexes in array. I think the only way is doing the segment tree with pointers and dynamically. It would be possible to use a segment tree in an array if it was possible to do a compression in the elements of the ordered sets (an offline solution), but I can't realize how to do that.
•  » » » 5 years ago, # ^ | ← Rev. 4 →   I mean that we have a vector, that contains nodes. Root has index 0. When we add child, we do push back in end and save value (int)tree.size()-1 as index of child.UPD: Accepted with 52 MB memoryUPD 2: Accepted with 26 MB memoryAs you can see, optimizations of using memory, which I said, works
•  » » » » Wow, thank you! It was really helpful
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   It was helpful for me too, because I did not know about Dynamic Segment Tree before, can you provide a list on problems which can be easy solved with this structure, maybe on coseforces?And your solutions works in O(mlog(n)) time
•  » » » » » » I didn't know this structure before this problem. In fact, I'm doing a list that my teacher gave me and there is only this problem about dynamic segment trees there, but there is a post from three years ago in codeforces with another problems: https://codeforces.com/blog/entry/19080Yes, I realized that my solution works in O(m*logn). I think it would work in O(m*logn²) if I used updateSegTree(query(num,Root,1,n),-1,Root); but as I did q = query(num,Root,1,n); and after updateSegTree(q,-1,Root,1,n); it works in O(m*logn). Is it correct?
•  » » » » » » » On each set or get query you add new log(n) vertices, so it is O(m * log(n)), thanks for link