[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 143 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
264(1): 2023/12/22(金)09:09 AAS
マージテクの方、マージする際に小さい方から大きい方の連想配列に照会する、じゃないとO(NQ)になるのでは
265: 2023/12/22(金)09:29 AAS
>>264
想定は連想配列もマージしていた
連想配列をマージしていれば、大→小のアクセス回数が小集合の頂点数と等しくなる
計算量は各頂点ごとの「照会を受ける回数」を考えれば全体でO(NlogN)
連想配列のマージはよくあるクエリ数の大←小のマージでよくて全体でO(QlogQ)
連想配列をマージしない場合、二乗の木DPみたいにO(N^2)かかりそうじゃない？
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 1.311s*