PREFIXOR, SnackDown 2017 Online Elimination Round 解法案

SnackDown 2017 Online Elimination Round
Prefix XOR (PREFIXOR)

https://www.codechef.com/SNCKEL17/problems/PREFIXOR
https://www.codechef.com/viewsolution/14319736

問題

非負整数列A[1]..A[n]が与えられる。次のオンラインクエリに答えよ
(l, r)：次の条件を全て満たすペア(i, j)の個数を出力せよ。

1. l<=i<=j<=r
2. 任意のk (i<=k<=j-1)について、(A[i]^A[i+1]^...^A[k]) <= (A[i]^A[i+1]^...^A[k+1])。^はxor。

n, q <= 400000

解法

前処理で各インデックスiから最大どこまで伸ばせるか求めておく。

A[i]^...^A[k] <= A[i]^...^A[k+1]を満たすのはA[k+1]の最上位ビットが(A[i]^...^A[k])では0のとき。
なので、A[i]^...^A[k]をA[k+1]まで伸ばせなくなるようなkの候補は、

cut[d][t] := i+1 : A[i]の最上位ビットがdビット目で、
    t==0なら(A[1]^...^A[i]) < (A[1]^...^A[i+1])、
    t==1なら(A[1]^...^A[i]) > (A[1]^...^A[i+1])

このcut[30][2]の60箇所だけ見ればよい。

どこまで伸ばせるかの列B[1]...B[n]ができたら、クエリ(l, r)に対する答えは

sum{l<=i<=r} min(B[i]-i, r+1-i)

である。
Range Tree（ソート列を持つSegment tree、Merge sort tree、特定の名前があるか不明）に持たせてクエリにそれぞれO(log^2 n)で答える。