It's so strange. I can never get to the link http://codeforces.com/problemset/problem/1304/D . But other links are OK. Can anyone tell me why or how I can solve it? Thank you.

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

1 | MiFaFaOvO | 3681 |

2 | Um_nik | 3544 |

3 | maroonrk | 3431 |

4 | tourist | 3409 |

5 | apiadu | 3397 |

6 | 300iq | 3317 |

7 | ecnerwala | 3260 |

7 | Benq | 3260 |

9 | LHiC | 3229 |

10 | TLE | 3223 |

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

1 | Errichto | 194 |

2 | antontrygubO_o | 191 |

3 | vovuh | 178 |

4 | pikmike | 174 |

5 | tourist | 166 |

6 | McDic | 164 |

6 | Um_nik | 164 |

8 | ko_osaga | 163 |

9 | Radewoosh | 162 |

10 | 300iq | 156 |

**Why can we put the option onto a segment tree? What do the segment tree do?**

Thank you

**Hello!**

You may have met these kinds of problems that require you to calculate the prefix sum with modifying, and you can use a fenwick tree *SUM* in order to solve it. When you want to lower_bound on it, you can reference this way as follows: You wonder the minimum *index* in the array *SUM[L~R]* satisfied *SUM[index]≥K*.

Set l=0, r=R, mid=R three pointers as the left, right, middle. If log2(r-l) is a positive interger, mid = (r - l)/2, or mid = pow(2, ceil(r-l) ) + l. If SUM[mid]≥K, r = mid, or l = mid. Continue to do it if l < mid < r. In the end, index = mid.

For this algorithm, it's not difficult to prove that the time complexity is about log2(R). You can understand it better with the help of this picture. And also you can solve such problems with a segment tree If there is something wrong with my algorithm, please tell me. Thanks.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/25/2020 15:20:56 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|