IF you have ranges and you want to query on how many elements in this range but every cell have to contain at most one element and the updates are on the range whether be +1 or -1. this could be done with segment tree and how ?

Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

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

1 | Radewoosh | 3759 |

2 | orzdevinwang | 3697 |

3 | jiangly | 3662 |

4 | Benq | 3644 |

5 | -0.5 | 3545 |

6 | ecnerwala | 3505 |

7 | tourist | 3486 |

8 | inaFSTream | 3478 |

9 | maroonrk | 3454 |

10 | Rebelz | 3415 |

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

1 | adamant | 173 |

2 | awoo | 167 |

3 | SecondThread | 163 |

4 | BledDest | 162 |

4 | Um_nik | 162 |

6 | maroonrk | 161 |

6 | nor | 161 |

8 | -is-this-fft- | 150 |

9 | Geothermal | 146 |

10 | TheScrasse | 143 |

IF you have ranges and you want to query on how many elements in this range but every cell have to contain at most one element and the updates are on the range whether be +1 or -1. this could be done with segment tree and how ?

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/01/2023 15:21:44 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

What is the query supposed to answer?Number of elements in the range?

Are you talking about unique elements in range? Also, +-1 on range or on one element?

1- +1/-1 to all the elements in a given range. (update) 2- i am talking about the number of non-zero elements in a given range. (query)

I believe it can't be easily done using a segment tree. Though you can make an sqrt-decomposition of your array where for each block store cnt[] map of elements and a modifier to add to all of them. On update, add +-1 to the modifier for each block that lies entirely inside the range, and manually go through and change all remaining elements (and according cnts). On query, sum cnt[-modifier] for all inside blocks and manually count all remaining elements (not forgetting about their blocks' modifiers). Thus you'll count all zero elements, so subtract it from the range's length to get the count of non-zero