In this explanation, for integers \(0 \leq c < B^{L}\), let \(N_{c}[i]\) represent the \(B^{i}\)-th digit when \(c\) is expressed as an \(L\)-digit number in base \(B\).

We consider the following lemma for pairs \((x, y)\) consisting of integers \(0 \leq x, y < L\).

Lemma

Consider pairs \((a, b)\) of integers \(0 \leq a, b < B^{L}\) that satisfy all of the following:

• \(a < b\)
• The maximum \(i\) such that \(N_{a}[i] \neq N_{b}[i]\) is \(x\)
• Among all \(i\) where \(N_{a}[i] \neq N_{b}[i]\), the index \(y\) maximizes \(P[i]\)

Find the number of pairs where \(A[a] > A[b]\) minus the number of pairs where \(A[a] < A[b]\).

Case: \(x \neq y\)

Let \(a'\) and \(b'\) be the integers obtained by swapping the \(B^{y}\)-th digit of \(a\) and \(b\). Formally, define \(a'\) and \(b'\) as follows:

• \(a' = a - B^{y} \cdot (N_{a}[y] - N_{b}[y])\)
• \(b' = b - B^{y} \cdot (N_{b}[y] - N_{a}[y])\)

In this case, there is a one-to-one correspondence between the pairs \((a, b)\) and \((a', b')\). Furthermore, \(a' < b'\) always holds. For the two pairs \((a, b)\) and \((a', b')\), exactly one of \(A[a] < A[b]\) or \(A[a'] < A[b']\) is true. Thus, the answer to the lemma is \(0\).

Case: \(x = y\)

Let \(z\) denote the number of integers \(i\) satisfying \(i < x\) and \(P[i] < P[x]\). Also, let \(I\) be the number of inversions in \(V_{x}\). Then, the following two points hold:

• The total number of pairs \((a, b)\) is \(\dfrac{B^{L + z}(B - 1)}{2}\)
• The number of pairs \((a, b)\) where \(A[a] > A[b]\) is \(B^{L - 1 + z}I\)

Thus, the answer to the lemma is:

\[ \dfrac{B^{L - 1 + z}(4I - B(B - 1))}{2}. \]

Final Answer to the Problem

Let \(S\) be the sum of the answers to the lemma for all \((x, y)\). Then the final answer is given by:

\[ \dfrac{1}{2}\left(S + \dfrac{B^{L}(B^{L} - 1)}{2}\right). \]

Therefore, if we can compute the answer to the lemma for all pairs \((x, y)\) where \(x = y\), we can obtain the final answer.

The time complexity to compute the number of integers \(i\) satisfying \(i < x\) and \(P[i] < P[x]\) for all \(x\) in \([0, L)\) is \(O(L\log{L})\).

The time complexity to compute the number of inversions in \(V_{0}, V_{1}, \dots ,V_{L - 1}\) is \(O(BL\log{B})\).

Since these are the bottlenecks, the overall time complexity is:

\[ O(L(B\log{B} + \log{L})). \]