I wish to extract the distinct elements in a given range of an array for queries L,R.
I used a Segment Tree of sets for the purpose.The time is within bounds, however it gives Memory Limit Exceeded. Any way to deal with the issue? Or any other approach otherwise.
1 Like
That sounds like a question on mo’s algorithm.
Won’t work.Constraints are 1<=N<=5e5
Do you have the question link?
The question is a part of another question that I’m working on.
Are the queries offline? If so, I have a solution for you, but you’ll have to verify that it’s not from an ongoing contest.
1 Like
Well it’s not from an ongoing contest. Now how do I verify that? I was basically practising Segment Trees.
I looked up this question:
And was wondering if I’ve to extract the elements as well, which doesn’t seem possible with a BIT(1D).
I wasn’t sure if Mo’s would be a great idea.So I wanted something faster.
And yes,they are offline with no updates.
To verify it, give the problem link. For example, “I’m solving the problem ATM and have a bug, etc.” so we know it’s in an archive rather than from a contest.
Yes, that is a good way to solve it. And it’s impossible to extract the elements, because you could have O(n) distinct elements per query. If you have to extract the elements, you might as well naively check the whole range.
1 Like
I attached the link in my comment above.
So you’re saying it’s rather impossible to extract all of them.Well,okay, cz I wont’t be trying any further then.Thanks for the help.