0

I am trying to solve cses salary queries (https://cses.fi/problemset/task/1144/)

Question: I will make a frequency array of salaries and I will use coordinate compression but while update I have to rebuild coordinate compression and there will be a mess.

How to solve this type of problem? I saw a blog in stackoverflow but I could not implement that solution of implicit segment tree.

Improve this question

1 Answer 1

Reset to default
0

The solution to your problem is very simple. Instead of coordinate compressing just the initial array, build a new array which is the union of the intial array and all the update query values. Perform coordinate compression on this instead. Your array size will be atmost N+Q. To perform update queries, simply find the compressed equivalent of the update query value.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.