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

Why do you indent your code so weirdly?

Sorry for the bad habits :) Is it better? https://ideone.com/e.js/jLFIMv

Auto comment: topic has been updated by noobinho (previous revision, new revision, compare).Auto comment: topic has been updated by noobinho (previous revision, new revision, compare).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.

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

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)) timeI 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/19080

Yes, 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 linkIs there an offline solution to this problem? In the comments (at the forum of the online judge) a person argued that he did a solution in O(m*logm). If it isn't an offline solution, how to do that?

Up!

I'm very curious to know if there exists an offline solution to this problem

Deleted

Auto comment: topic has been updated by noobinho (previous revision, new revision, compare).