Problem: https://www.codechef.com/problems/HLD/
I was only able to come up with the simple O(n^2) DP. I went through the editorial but didn't fully understand it.
Can someone share their ideas/approaches.
Any help would be appreciated.
Problem: https://www.codechef.com/problems/HLD/
I was only able to come up with the simple O(n^2) DP. I went through the editorial but didn't fully understand it.
Can someone share their ideas/approaches.
Any help would be appreciated.
Problem: Given an array answer queries(online) of the form [L,R]=number of distinct elements in the array from index L to R.
What different approaches/solutions are there to this problem.
Few approaches I know/heard of:
1.Using Segment/Merge-Sort tree (link:https://stackoverflow.com/questions/39787455/is-it-possible-to-query-number-of-distinct-integers-in-a-range-in-olg-n)
2.Modified Sqrt Decomposition (link:https://codeforces.com/blog/entry/44711?#comment-292719)
Are there any other interesting ways.
Also, what if we have update queries as well. (The above approaches will also work for updates but are there any other ways)