競技プログラミングにハマるプログラマのスレ 143

[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 143 (1002ﾚｽ)
上下前次1-新
抽出解除ﾚｽ栞

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索歴削→次ｽﾚ栞削→次ｽﾚ過去ﾛｸﾞﾒﾆｭｰ

378(3): 2023/12/22(金)17:40 AAS
クエリを
P[i]とP[j]をswapしてから、P[x]の値がk以上のすべての添字xに各1罰を与える
に変えれば平面捜査できなくなるよな？
でも並列二分探索ならlog2個で解けるはず
難易度はARC-Cくらいやろ

385: 2023/12/22(金)19:01 AAS
>>378
おー綺麗な問題

387: 2023/12/22(金)19:17 AAS
>>386
>>369の質問を添字x→値xに変更するだけなら解けると思う
>>378よりは僅かに簡単

458(1): 2023/12/22(金)23:42 AAS
並列二分探索やっと理解した
>>378は罰クエリの回数をM、質問クエリの回数をQとすると、Pの逆置換を持っておけば罰クエリは双対セグ木で1回辺りO(logN)で処理できるから全体O(logM･(M+Q)logN)であってる？