CodeChef Strange Transform

問題文

https://www.codechef.com/problems/STRTF

問題概要

長さ N の数列 A がある. f(A) は i 番目の要素が A[i] XOR A[i+1] となる数列とする.
Q 個のクエリ (k, x) が与えられるので f^k(A) の x 番目の要素を求めよ.
N ≦ 2e5, Q ≦ 2e5, k ≦ 1e9, x ≦ N

解法

f^k(A)_0 がどの位置の値を XOR したものになるかを観察すると, 2冪ごとに 100....01 みたいな感じになる.
フラクタルっぽい感じ.
なので上のbitから再帰で計算してやると, 各クエリで 2^(bit count(k) ) くらいで求まるけど, それでは全然間に合わない.

よく考えると, kの上の方のbitは関係なくて, 下位18bitだけ見ればよい.
さらに, 前処理で各位置 x について k < (1<<9) で f^k(A)_x を求めておくと, 残りの上 9 bitだけの再帰になるので, 各クエリ 2^9 で間に合う.

つまり計算量 O(N sqrt N+Q sqrt N).
これ log とかで解けたりしないのかな.

ソースコード

https://www.codechef.com/viewsolution/21426207

#include <bits/stdc++.h>
using namespace std;

const int B = 18;
const int hB = B >> 1;
const int MAX = 1 << B;

int N;

int dp[1 << hB][MAX];

int calc(int i, int x) {
    if (i >= N) return 0;
    if (x < (1 << hB)) return dp[x][i];
    int t = 31 - __builtin_clz(x);
    int tx = x - (1 << t);
    return calc(i, tx) ^ calc(i + (1 << t), tx);
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    int Q;
    cin >> N >> Q;
    for (int i = 0; i < N; i++) {
        cin >> dp[0][i];
    }
    for (int j = 1; j < (1 << hB); j++) {
        for (int i = 0; i < N; i++) {
            dp[j][i] = dp[j - 1][i] ^ (i + 1 < N ? dp[j - 1][i + 1] : 0);
        }
    }
    while (Q--) {
        int K, X;
        cin >> K >> X; --X;
        K &= (1 << B) - 1;
        printf("%d\n", calc(X, K));
    }
    return 0;
}