ABC253 C - Max - Min Query
で、解説を見たら、
例えば c++ なら std::multiset を用いることにより高速に処理できます
とか言われて、??? となったので、調べた。
multiset とは
日本語だと、多重集合。 問題文にも書いてあった。
Rust でどうやるか、だが、下の記事を参考にすると、
- 要素の管理を HashMap でやる
- 最小値と最大値は BtreeSet でやる
でできるらしい。
BTreeSet は
An ordered set based on a B-Tree.
なので、最小値と最大値がすぐに求められる。
TLEになったやつを、BTreeSet使って最大値と最小値を求めるように修正して提出したら、無事に通った。
なお、最大値は、nth(len() - 1)
ではなく、last()
で取得しないと通らない。
提出したやつ。