setでlower_boundする時の注意点(C++)
最近ハマった罠なので紹介します。(このブログにはrupc2018 day1 problem G Elevatorの解説が含まれています)
事の発端
私は第16回JOI春合宿に出場してから競プロをすっかり止め、受験勉強に専念していました。ク☆やオルガにハマったりと危ない時期もありましたが何とか大学に合格できました。「これまでの遅れを取り戻さないと・・・」と思いながら競プロを再開したときに事件は起こりました。
RUPC
MMNMM(@259_Momone)にこんな問題を紹介されました。
https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp18Day1/problems Problem G Elevator
私の解放は次のようなものです。
まず初めにエレベーターを設置するクエリと質問のクエリを日付でソートし先頭から順に見ていきます。それがエレベーターのクエリの場合を考えます。もしある二つのエレベーターi,jがあって、[A_i,B_i]と[A_j,B_j]が交わっていればエレベーターi,jの代わりに[min(A_i,A_j),max(B_i,B_j)]の範囲を持つエレベーターを追加することができます。したがってエレベーターを追加するときは、そのエレベーターの範囲と交わっているエレベーターを削除し、代わりに削除したエレベーターと新しく追加するエレベーターの役割と同じエレベーターを追加します。これはpairのsetで高速に実装することができます。次に質問のクエリが来た場合ですが、S_i>=T_iならばエレベーターを使わずにそのまま下りればよく、そうでない場合はS_iとT_iの両方を含む範囲があるか探し、あればYes、なければNoを出力すればいいです。これもpairのsetで高速に実装できます。以上でこの問題がO( (M+Q)log(M+Q))で解くことができます。
コード書くぜ！(ガタッ)
久しぶりの競プロということもあって意気揚々とコードを打ち込み始めました。書き終えてsubmit!しかし判定は…
あれ？丘people!?計算量はクリアしているはずなのに…。計算量は合っているという自信の元、適当な定数倍高速化を施しつつsubmitしました。
(↑さいーやく)
行き詰っているとMMNMMから指摘を受けました。「lower_boundの使い方間違ってない？」
lower_boundには2種類ある！
set<int> s;
int x;
①auto ite=lower_bound(s.begin(),s.end(),x);
②auto ite=s.lower_bound(x);
みなさんは①と②のどちらが正しいコードかわかりますか？僕は①を書いていたのですが実は②が正しいんですね～。
①のlower_boundではどういった事が起きているかを解説します。gcc7.3.0ではlower_boundは次のような感じで実装されています。
iterator lower_bound(iterator first,iterator last,x){
len = distance(first,last);
while(len > 0){
half = len>>1;
middle = first;
advance(middle,half);
if(*middle < x){
first = middle;
++first;
len -= half+1;
}else{
len = half;
}
}
return first;
}
ここでdistance(first,last)はfirstとlast距離を求める関数、advance(middle,half)はイテレータmiddleをhalf回1進める関数です。もしfirstやlastがvectorなどのイテレータだったらdistanceもadvanceもO(1)で求めることができますが、setのイテレータは1ずつしか動かせないためO(N)かかってしまうため全体でO(NlogN)の計算量となってしまいます。(O(NlogN)の探索とか絶対いらないので①みたいなコード書いたらエラー出すような仕様になってほしい)
訂正:O(NlogN)→O(N)
advanceで進む回数はN/2+N/4+N/8+・・・1=Nとなるので。
②に直したら通りました。(やったぜ)
まとめ
lower_boundには気を付けよう！
