2015-03-30から1日間の記事一覧

今日の典型データ構造(上級編)

uwiさんから 長さNの、整数列(全部の要素が1 ~ N, 全部の要素はdistinct)に対して以下のクエリがQ個飛んでくる l, rが与えられるから, l番目~r番目の数列を切り出した時、それの転倒数を求める N = Q = 100,000 TLE2s 重要事項 僕はまだ解法を考えてないです…

今日の典型データ構造

長さNの、bool列(全部の要素が0 or 1)に対して以下のクエリがQ個飛んでくる l, rが与えられるから, l番目~r番目の数列を切り出した時、それの転倒数を求める l, rが与えられるから, l番目~r番目の要素を全部反転させる(0だったら1に, 1だったら0に) N = Q = …

RBST(Randomize Binary Search Tree)の計算量について考えてみた

RBSTは万能かつ簡潔な平衡二分木として有名ですね Q.でもこれって計算量どうなんやろ A.なんかいい感じやねんのままだとよくないかなぁと思ってちょっと考えてみました注意点として今回の記事では全部i番目というのは0-indexedです あと、スピリチュアルです…