You have an array $$$arr$$$ with $$$n$$$ elements. Let number $$$i$$$ occurs in multiset $$$Q$$$ $$$arr_i$$$ times. How to get random number from multiset $$$Q$$$ faster than $$$O($$$$$$\log n$$$$$$)$$$?

$$$n$$$ <= $$$1e5$$$, $$$arr_i$$$ <= $$$1e9$$$

Объясните, как определяется рейтинг стран/городов/организаций? Рейтинг России, например, составляет 3132, а Москвы и Питера — 3055 и 2819. Как это работает?