Hi ... Is there a way to find the number of different integers within a range of log(n) complexity?

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

1 | Benq | 3783 |

2 | jiangly | 3666 |

3 | tourist | 3611 |

4 | Um_nik | 3536 |

5 | inaFSTream | 3477 |

6 | fantasy | 3468 |

7 | maroonrk | 3464 |

8 | QAQAutoMaton | 3428 |

9 | ecnerwala | 3427 |

10 | Ormlis | 3396 |

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

1 | Um_nik | 184 |

2 | adamant | 178 |

3 | awoo | 177 |

4 | nor | 169 |

5 | maroonrk | 165 |

6 | -is-this-fft- | 164 |

7 | antontrygubO_o | 152 |

8 | ko_osaga | 151 |

9 | dario2994 | 150 |

10 | SecondThread | 149 |

Hi ... Is there a way to find the number of different integers within a range of log(n) complexity?

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/07/2023 14:40:22 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

use a map may be bro

Maybe.. but I don't think so

its so slow...

Use a segment tree. Whenever you add a new element set its value as 1. When you want to know how many values in range [l,r] you can get the sum of the range (l,r)

Thanks

Wait, what do you mean by range? Is it a subarray or a range of numbers?

hey we can use map also ?

You can use, but that way is be slower than segment tree. You can also use set. But it is also slow...

Hint: Offline+Fenwick.

https://cses.fi/problemset/task/1734

make array nxt[i] that means index of number that equal a[i] if there are no such set INF

then for answer u need to find number of nxt[i] that less r on range l<=i<=r

use Segment tree

He wants in O(logn) complexity. Your's is O(log^2n).

Hello freind you can simply use 1 pointer technique to solve this. Move your lazy ass pointer finger and count whatever you want in the segment

Persistent segment tree if you need online, else Fenwick and offline