So far I have tried this code but couldn't approach to the optimised way of solving the problem. A small hint would be a great help instead of complete solution.

Link to the problem : https://cses.fi/problemset/task/2416

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

1 | tourist | 3690 |

2 | jiangly | 3647 |

3 | Benq | 3581 |

4 | orzdevinwang | 3570 |

5 | Geothermal | 3569 |

5 | cnnfls_csy | 3569 |

7 | Radewoosh | 3509 |

8 | ecnerwala | 3486 |

9 | jqdai0815 | 3474 |

10 | gyh20 | 3447 |

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

1 | maomao90 | 171 |

2 | adamant | 164 |

3 | awoo | 163 |

4 | TheScrasse | 160 |

5 | nor | 157 |

6 | maroonrk | 155 |

7 | -is-this-fft- | 152 |

8 | Petr | 146 |

9 | orz | 145 |

9 | pajenegod | 145 |

So far I have tried this code but couldn't approach to the optimised way of solving the problem. A small hint would be a great help instead of complete solution.

Link to the problem : https://cses.fi/problemset/task/2416

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/24/2024 19:09:49 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Did you solved it ?

see dolphingarlic's explanation + solution

You can use segment tree to solve this problem.

Hint1Use it for the sum and max of range l..r

SolutionWhen query asks a range l r you can do the following steps. 1) start with range 1, n

2) go both children (you have to go first to left one)

3) if your current range is out of required range return 0

4) if your current range is complete in required range:

5) return sum of children

I don't think this is a correct solution. (or maybe I misinterpreted it)

If I have an array [0,2,4,0] and I want to query (1,4), this solution will yield 10 as answer. (while the answer should be 4)

You can try using binary lifting + monotonic stack. :) (Just a hint)

would you like to share your solution?

tysm for the hint man, solved it because of that.