Is there a way to find index of a element which is in set. between time complexity o(1)... o(log(n))

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

1 | tourist | 3735 |

2 | MiFaFaOvO | 3681 |

3 | Um_nik | 3553 |

4 | Benq | 3376 |

5 | ecnerwala | 3295 |

6 | maroonrk | 3229 |

7 | TLE | 3223 |

8 | Radewoosh | 3216 |

9 | scott_wu | 3209 |

10 | Petr | 3205 |

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

1 | Errichto | 200 |

2 | antontrygubO_o | 191 |

3 | pikmike | 188 |

4 | Monogon | 184 |

4 | vovuh | 184 |

6 | Ashishgup | 182 |

7 | Um_nik | 180 |

8 | Radewoosh | 173 |

9 | SecondThread | 172 |

10 | McDic | 161 |

Is there a way to find index of a element which is in set. between time complexity o(1)... o(log(n))

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/07/2020 15:57:42 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Check this

thanks!

use ordered_set

use the

`rb_tree_tag`

included in`ext/pb_ds/tree_policy.hpp`

; although you can use Binary Indexed Tree + Binary Search to do it in $$$O(\log^2n)$$$ time (I think it's faster), you even can do Binary Lifting (as a kind of binary search) to perform it in $$$O(\log n)$$$. The bad thing is when you must do it fully dynamic and the elements are ~$$$10^9$$$i think we may use lower_bound or upper_bound for o(log(n))

elaborate.

you can refer this

What the heck? You won't be able to get the index of the set using that. As mentioned above, the easiest way is to use PBDS. I assume your method only works if the set is

fixedwhich off-course, not applicable for most of the problems.That is incorrect +_+

STL won't work, The set in C++ STL uses bidirectional iterators, it's like a BST inside, you can't find the index of element in a set without using PBDS.

Aahan I realized that I misunderstood it, Can you provide how to use PBDS here?

PBDS Tutorial