[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 143 (1002ﾚｽ)

競技プログラミングにハマるプログラマのスレ 143 http://medaka.5ch.net/test/read.cgi/prog/1703141733/

上下前次1-新
通常表示 512ﾊﾞｲﾄ分割 ﾚｽ栞
抽出解除 ﾚｽ栞

---

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

---

378: 仕様書無しさん [sage] 2023/12/22(金) 17:40:10.87 クエリを P[i]とP[j]をswapしてから、P[x]の値がk以上のすべての添字xに各1罰を与える に変えれば平面捜査できなくなるよな？ でも並列二分探索ならlog2個で解けるはず 難易度はARC-Cくらいやろ http://medaka.5ch.net/test/read.cgi/prog/1703141733/378

385: 仕様書無しさん [sage] 2023/12/22(金) 19:01:13.52 >>378 おー綺麗な問題 http://medaka.5ch.net/test/read.cgi/prog/1703141733/385

387: 仕様書無しさん [sage] 2023/12/22(金) 19:17:15.84 >>386 >>369の質問を添字x→値xに変更するだけなら解けると思う >>378よりは僅かに簡単 http://medaka.5ch.net/test/read.cgi/prog/1703141733/387

458: 仕様書無しさん [sage] 2023/12/22(金) 23:42:27.12 並列二分探索やっと理解した >>378は罰クエリの回数をM、質問クエリの回数をQとすると、Pの逆置換を持っておけば罰クエリは双対セグ木で1回辺りO(logN)で処理できるから全体O(logM･(M+Q)logN)であってる？ http://medaka.5ch.net/test/read.cgi/prog/1703141733/458

---

ﾒﾓ帳

(0/65535文字)

---

上下前次1-新書関写板覧索設栞歴

---

ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

Google検索

Wikipedia

---

ぬこの手 ぬこTOP 0.479s*