初めに，解説で用いる記法などを定義します．

• 本解説において扱う対象は整数です
  • 単に \([l,r]\) などと書いた場合は \(l\) 以上 \(r\) 以下の整数からなる集合を考えていることとします
• 集合 \(S\) に対して（\(x\) との） XOR を取るとは，\(n \in S\) を満たす \(n\) を渡る \(n \oplus x\) からなる集合とします
• 記法として \(S \oplus x \coloneqq \lbrace n \oplus x \mid n \in S \rbrace\) を用います
• 非負整数 \(i,j\) に対して，\(S(i,j)\coloneqq[2^ij,2^i(j+1))\) とします
  • 特にこの \(S\) は配列長が \(2\) 冪であるようなセグメント木のノードが覆う区間を表しています
• 集合 \(S,T\) が \(S \lt T\) であるとは \(\forall x \in S, \forall y \in T;\; x \lt y\) が成り立つこととします
• 非負整数 \(K\) に対し \(K_i\) で \(K\) の二進法表記の \(2^i\) の位の数を表すこととします
• \(R\) に \(1\) を加算し，数列 \((L\oplus X, \dots, (R-1)\oplus X)\) を考えることにします

また，\(L_{i-1} \ne R_{i-1}\) なる最大の \(i\) を \(N\) とします．このとき

\[L \leftarrow L \bmod 2^N, R \leftarrow R \bmod 2^N, X \leftarrow X \bmod 2^N\]

としても答えに影響しないので以降このような条件を課すことにします．

[1] 数列を区間に分割する

まず，与えられる列 \((L\oplus X,(L+1)\oplus X, \dots,(R-1)\oplus X)\) を \(O(\log(R-L))\) 個の区間に分割をし，その区間ごとに転倒数を求めることにします．まず，重要な事実として以下を示します．

• 任意の非負整数 \(i,j,x\) に対して \(S(i,j)\oplus x\) は，ある非負整数 \(k\) を用いて \(S(i,k)\) と表すことができる

証明

$S(i,j)=\lbrace 2^ij+m \mid 0 \leq m \lt2^i \rbrace$ です．各 $y \in S(i,j)$ に対して $x \oplus y$ を考えると，$m$ の値に関わらず $2^i,2^{i+1},\cdots$ の位は一定で，これは $\underline{x} \coloneqq \lfloor x / 2^i \rfloor$ とすれば $\underline{x} \oplus j$ です． これにより，$\bar{x} \coloneqq x \& (2^i-1)$ ($x$ の下位 $i$-bit) とすれば $$S(i,j)\oplus x = \lbrace (2^ij+m) \oplus x \mid 0 \leq m \lt 2^i \rbrace = \lbrace 2^i(\underline{x} \oplus j)+(m \oplus \bar{x}) \mid 0 \leq m \lt 2^i \rbrace$$ です．よって $\lbrace (m \oplus \bar{x}) \mid 0 \leq m \lt 2^i \rbrace = [0,2^i)$ が示されれば良いです． これは写像 $f \colon [0,2^i)\to[0,2^i);m \mapsto m \oplus \bar{x}$ が全射であることから示されます（全射性は $[0,2^i)$ が有限集合であることと $f$ が単射であることから示されます）． 以上を合わせて，$S(i,j)\oplus x = S(i, j \oplus \underline{x})$ が示されました．

これにより，\([L,R]\) をセグメント木の要領で分割すれば \([L,R]\oplus X\) も \(O(\log (R-L))\) 個の区間に分割されます．以降これを \((S_k)_{k=1}^{K}=(S(i_k,j_k))_{k=1}^{K}\) とおきます（添え字は元の区間の昇順で並んでいるとします）．

[2] 区間同士の転倒数を求める

まずは異なる \(S_k\) に含まれる数による転倒数を求めます．これは \(S_k\) たちが disjoint であったから

\[\sum_{l=1}^{K}\sum_{\substack{k \lt l \\ S_k \gt S_l}}(\# S_k)(\# S_l)\]

と表されます．よって，各 \(k \lt l\) に対して \(S_k \gt S_l\) かが分かれば良いです． ここで，\(S_k\) が区間の分割であったから，ある \(k_0\) が存在して

\[i_1 \lt i_2 \lt \cdots \lt i_{k_0},\; i_{k_0+1} \gt \cdots \gt i_{K-1} \gt i_K\]

が成り立ちます．この \(k_0\) を用いて次の \(3\) つの場合に分けて \(S_k \gt S_l\) かどうかを判定します．

1. \(k \lt l \leq k_0\)
2. \(k \leq k_0 \lt l\)
3. \(k_0 \lt k \lt l\)

1 について

各 \(l\) に対して \(k \lt l\) かつ \(S_k \gt S_l\) が成り立つ \(k\) を考えます．

\(k (\lt l)\) を \(1\) つ固定します．セグメント木の構造を考えることで次が成り立ちます．

• \(\forall x \in S_k, \forall y \in S_l\) に対してこれらの \(2^{i_l}\) の位の数は異なり，\(2^{i_l + 1}, 2^{i_l + 2},\cdots\) の位の数は等しい

よって求めるべきは \(X\) の \(2^{i_l}\) の位の数が \(1\) であるような \(l\) 全てに対する \(\sum_{k \lt l} \lvert S_k \rvert \lvert S_l \rvert = \sum_{k \lt l}2^{i_k}2^{i_l}\) の和です．

これは，数列 \(A=(A_i)_{i=0}^{N-1},B=(B_i)_{i=0}^{N-1}\) をそれぞれ

\[A_i=\begin{cases} 1 \quad \big[\exist 1 \leq j \leq k_0, i_j=i \big] \land X_i=1 \\ 0 \quad otherwise \end{cases}\]

\[B_i=\begin{cases} 1 \quad \exist 1 \leq j \leq k_0, i_j=i \\ 0 \quad otherwise \end{cases}\]

と定めれば

\[\sum_{0 \leq i \lt N}\sum_{0 \leq j \lt i}A_iB_j2^{i+j}\]

となり，分割統治と畳み込みを用いて \(O(N (\log N)^2)\) で計算することができます．

2 について

\(2^{N-1}\) の位に着目することで，次のいずれかが成り立つことが分かります．

• 任意の \(k,l\) に対して \(S_k \lt S_l\)
• 任意の \(k,l\) に対して \(S_k \gt S_l\)

よって \(X_{N-1}=1\) のときに

\[\sum_{k \leq k_0 \lt l} \lvert S_k \rvert \lvert S_l \rvert = \sum_{k \leq k_0 \lt l} 2^{i_k}2^{i_l}\]

を加算すればよく，これは畳み込みによって \(O(N \log N)\) で求めることができます．

3 について

1 と同様の議論ができます

よって \(O(N(\log N)^2)\) で区間同士の転倒数を求めることができました．

[3] 区間内の転倒数を求める

あとは各 \(S_k\) 内の転倒数が求まれば良いです．これらの構造から次の部分問題を考えれば良いです．

\(n \gt 0\) について，数列 \((0 \oplus X, 1 \oplus X, \dots, (2^n-1)\oplus X)\) の転倒数はいくつですか．

次の操作を考えます．

• 長さ \(2^n\) の数列を \(A\) を \(A=(0,1,\dots,2^n-1)\) で初期化する
• \(i=0,1,\dots,n-1\) の順に \(X\) の \(2^i\) の位の数 \(1\) のとき各 \(A_j\) を \(A_j \oplus 2^i\) で置き換える

求めたいのは操作後の \(A\) の転倒数です．「各 \(A_j\) を \(A_j \oplus 2^i\) で置き換える」という操作を操作 \(i\) と呼ぶことにします．全ての \(i\) および \(j_1 \lt j_2\) について次が成り立ちます． - \(\lfloor j_1/2^{i+1} \rfloor \lt \lfloor j_2/2^{i+1} \rfloor\) ならば操作 \(i\) の直後において \(A_{j_1} \lt A_{j_2}\) - 操作 \(i\) の直前に \(A_{j_1} \gt A_{j_2}\) ならば操作 \(i\) の直後でも \(A_{j_1} \gt A_{j_2}\)

証明

$1$ つ目は明らかです． $2$ つ目について，操作 $i$ によって $A_{j_1} \lt A_{j_2}$ となったとすれば，$A_{j_1}$ の $2^i$ の位が $1$，$A_{j_2}$ の $2^i$ の位が $0$ であり，$2^{i+1},2^{i+2},\dots$ の位が等しいですが，これは $1$ つ目に矛盾します．

結局，各操作 \(i\) の前後で \(A_{j_1}\) と \(A_{j_2}\) の大小が変化する \(j_1,j_2\) の個数が求まればよく，これは \(2^{n-1-i}\times (2^{i})^2=2^{n-1+i}\) です．よって，部分問題の答えは

\[\sum_{\substack{i \lt n \\ X_i=1}}2^{n-1+i}=2^{n-1}\sum_{\substack{i \lt n \\ X_i=1}}2^{i}\]

となります．

これを各区間について足しあげれば良いので，求めるべきは

\[\sum_{\substack{k=1 \\ i_k \gt 0}}^{K}2^{i_k-1}\sum_{\substack{j \lt i_k \\ X_j = 1}}2^j\]

となります．

これは数列 \(A=(A_i)_{i=1}^{N-1},B=(B_i)_{i=0}^{N-1}\) をそれぞれ

\[A_i=X_i,B_i= \#\lbrace 1 \leq k \leq K \mid i_k=i \rbrace\]

と定めれば

\[\sum_{1 \leq i \lt N}\sum_{0 \leq j \lt i}A_iB_j2^{i+j-1}\]

となり，[2]-1 と同様に分割統治と畳み込みを用いて \(O(N (\log N)^2)\) で計算することができます．

以上から，各テストケースについて \(O(\log L + \log R + \log X + N (\log N)^2)\) でこの問題を解くことができました．

実装例(C++)