Atcoder水色精進記録
ABC231
F - Jealous Two
https://atcoder.jp/contests/abc231/tasks/abc231_f
アルゴリズム・データ構造
SegmentTree, 2分探索
考察
とりあえずAだけで考えてみる
Aを逆順にsortして高橋くんへのプレゼントを固定して考えてみると
高橋くんへのプレゼント(idx=Xとする)に選んだAより右にあるAは高橋くん側の条件を満たす。
青木くんの条件を満たすには、Xより右側にあるもののうち、Bx以上のBである。
Bのリストを事前にsortしておけば、2分探索でBx以上のBの個数は判定することが出来る。
そのうち右側にあるという条件はどうすればいいか?
反対に考えて、左側にあるB以上のBを数えることができればOK
→OrderdListや座標圧縮したSegtreeなどで、左側の項目を管理すればいけそう
Xより左にある、Axと同じAのプレゼントは青木くんへのプレゼントに選んでも、高橋くんの条件は満たすため、Xが変わったタイミングでSegtreeを更新としなければならない(入力例 3のケース)
計算量としては、
Xの探索がN
Bx以上のBの個数の判定がlogN
SegTreeの更新・取得がlogN
A,BのsortがNlogN
NlogN＋(N-1)(logN+logN)→NlogN
提出
感想
SegmentTreeが空で実装できるようになってきた。
簡単なSegmentTreeの使い方も身についてきた気がする。