Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

arbcrt040's blog

Tree Multiset
By arbcrt040, history, 11 years ago, In English

Hello guys :)

I've read this blog by adamant. So my question is: Is there a way to get kth number in a multiset. Thanks in advance.

(Sorry for bad English)

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
11 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

you can transform any set into multiset. Just like in adamant's example:

typedef tree<pair<int, int>, ...> ordered_set;

ordered_set X;
int cnt = 0;

X.insert({1, cnt}); cnt += 1;
X.insert({1, cnt}); cnt += 1;
X.insert({2, cnt}); cnt += 1;

cout << X.find_by_order(1)->first << endl; // 1
cout << X.order_of_key({2, 0}) << endl; // 2
→ Reply