Not Quick Transformation (Codeforces 117D)

http://codeforces.com/problemset/problem/117/D

問題

1からnまでの数列がある。この数列に対して奇数番目の数値を前半に、偶数番目の数値を後半に移動させる操作Fを再帰的に作用させる。この変換によってできた数列をbとする。各クエリに対して

を求めよ。

解法

最初の数列は初項1、公差1の等差数列になっている。初項x、公差dの長さnの等差数列に対してFを1回だけ作用させると前半部分は初項x、公差2dの長さ(n+1)/2の等差数列になる。後半部分は初項x+d、公差2dの長さn/2の等差数列になる。
なのでクエリの範囲が等差数列をすべて覆うまで再帰的にFを作用させ、全て覆ったら等差数列を使って一気に値を計算すれば良い。セグメントツリーを使ったRMQとかと同様にO(logn)で計算できる。