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 | 4009 |

2 | jiangly | 3823 |

3 | Benq | 3738 |

4 | Radewoosh | 3633 |

5 | jqdai0815 | 3620 |

6 | orzdevinwang | 3529 |

7 | ecnerwala | 3446 |

8 | Um_nik | 3396 |

9 | ksun48 | 3390 |

10 | gamegame | 3386 |

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

1 | cry | 164 |

1 | maomao90 | 164 |

3 | Um_nik | 163 |

4 | atcoder_official | 160 |

5 | -is-this-fft- | 158 |

6 | awoo | 157 |

7 | adamant | 156 |

8 | TheScrasse | 154 |

8 | nor | 154 |

10 | djm03178 | 153 |

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: Nov/12/2024 12:12:40 (k2).

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.