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.

# | User | Rating |
---|---|---|

1 | tourist | 3557 |

2 | Um_nik | 3494 |

3 | Radewoosh | 3344 |

4 | wxhtxdy | 3309 |

5 | LHiC | 3302 |

6 | Benq | 3286 |

7 | mnbvmar | 3274 |

8 | Petr | 3254 |

9 | yutaka1999 | 3190 |

10 | ksun48 | 3170 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 191 |

2 | Radewoosh | 180 |

3 | PikMike | 165 |

3 | antontrygubO_o | 165 |

3 | Vovuh | 165 |

6 | rng_58 | 161 |

7 | majk | 156 |

7 | Um_nik | 156 |

9 | 300iq | 155 |

10 | farmersrice | 151 |

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)

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/14/2019 12:26:40 (e1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|