htkb-proconの日記

初心者がPythonで問題解いた記録

Codeforces Round #416 (Div. 2) B 平方分割

B. Vladik and Complicated Book

適当訳:数列と3つの数字からなるクエリl, r, xが与えられるので、元の数列とそれのl番目からr番目までを昇順にソートした数列を比べて、x番目の数字が変わってないか調べてNE!

数列 5 4 3 2 1
クエリ 1 3 1 → 変換済み数列 3 4 5 2 1 → 1番目は元の数列と違うので No
クエリ 2 4 3 → 変換済み数列 5 2 3 4 1 → 3番目は元の数列と同じなので Yes

f:id:htkb:20170530205829j:plain

_人人人人人人人人人人人人人人人人人人_
> あ!これ蟻本でやったところだ!! <
 ̄Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y ̄

でも覚えてなかった!!平方分割してそれぞれのバケットごとにソートするのは覚えてたんだけど、そこからわからなくてWAとTLEを食らった。跨いでる各バケットについて二分探索するんだった。

元の数列 1 7 4  3 9 2  6 5 8
√n個のバケットに分割してソート
バケット[1 7 4][3 9 2][6 5 8]
↓
ソート  [1 4 7][2 3 9][5 6 8]

クエリ 3 8 5 の場合:元の数列の5番目の数は 9
3〜8番目の中でまるまる含まれているバケット(この例では2番めのバケット)について
二分探索などで9が各バケット内の何番目こに入るか高速に調べる。
           ↓ここ!
    [ 2  3  9 ]

バケットの一部しか含まれない左右の部分は、元の数列から引っ張ってきて
くっつけてソートし、同じように何番目に入るか調べる。
左の切れ端 右の切れ端
    [ 4 / 6 5 ]
         ↓
    [ 4  5  6 ]
             ↑9が入るのはここ!

つまりソート部において9の左に5個数字がある=ソート部の6番目に入る
=ソート開始地点より左の2つも合わせて、変換済み数列の8番目に9がくる
元の数列では5番目だったので答えは No

pythonならばbisectモジュールのbisect_left()を使うことで簡単にある数字がリストのどこに入るのか二分探索で調べてくれる。
提出コード(汚い):http://codeforces.com/contest/811/submission/27383788

蟻本に載ってるPOJの問題はこちら 2104 – K-th Number