[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 143 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
476(1): 2023/12/23(土)00:42 AAS
>>474
ノードごとswapってできるの？
swapクエリを処理するにつれて順列はシャッフルされてゆくから、値k以上のすべてにaddの計算量が死ぬだろ
遅延に「ノードの値がk以上なら1加算」の処理を載せてlogNに抑える方法ないし
478(2): 2023/12/23(土)00:55 AAS
>>476
各クエリでP[x]番目のノードとP[y]番目のノードをswapすればノードの並びが常にPの逆置換になってくれて1回の区間加算で処理できると思うんだけど(でも結局外に添字と値の対応を表す配列を持たなきゃいけないのでその配列で罰数も管理する方が自然なのかも)
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.027s