C21's blog

By C21, history, 5 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +11
  • Vote: I do not like it

By C21, history, 5 years ago, In English

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)

Full text and comments »

  • Vote: I like it
  • +8
  • Vote: I do not like it