We are solving problem in range $$$[1, ..., R]$$$. Let's split this range into $$$O(10*log_{10}R)$$$ smaller ranges. Let's fix the prefix of this number and the following digit. Then we have a choise for the last $$$k$$$ digits and the amount of numbers in this range is $$$10^k$$$. For example, if $$$R = 2643$$$ and we fixed one digit and set the next one to 4, we have a range $$$[2400, ..., 2499]$$$. Let's split inversions in following 3 types:

1) Inversions on a prefix. We can compute them by hand and multiply by $$$10^k$$$ — for each number in the range. In our case we have one inversion on a prefix and it appears in 100 numbers.

2) First digit of inversion is on prefix, but second isn't. Then, let's fix this digit on prefix (its position). If the digit we fixed is $$$a$$$, we have $$$9 - a$$$ digits that are more than $$$a$$$. In $$$10^k$$$ numbers from $$$[0, ..., 10^k - 1]$$$ (with leading zeroes) each of this digits appear with probability $$$\frac{9 - a}{10}$$$ on each of $$$k$$$ positions — on each position independently. So, there are $$$(9 - a) * 10^{k - 1} * k$$$ inversions with digit $$$a$$$. In range $$$[2400, ..., 2499]$$$ there will be $$$5 * 10 * 2$$$ inversions with $$$a = 4$$$ and $$$7 * 10 * 2$$$ inversions with $$$a = 2$$$.

3) Both digits of inversion aren't on prefix. Amount of them is the same as amount of invertions in $$$[0, ..., 10^k - 1]$$$ (each number with leading zeroes). We can precompute this number for each $$$0 \leq k \leq 14$$$ by fixing the first digit and using already computed values.

After this, we have to check numbers with $$$number$$$ $$$of$$$ $$$digits$$$ $$$<$$$ $$$number$$$ $$$of$$$ $$$digits$$$ $$$in$$$ $$$R$$$. This values can be precomputed, too.

My submission. I hope that it helped you.

In this case we need to calculate distance between $$$V$$$ and $$$L$$$. Let's do it in the following way:

Define $$$Level_U$$$ as the depth of vertex $$$U$$$ in the centroid decomposition tree. It is well known, that on each path $$$XY$$$ there is exactly one vertex with the minimum level. Define $$$Parent_U$$$ as the parent of $$$U$$$ in the centoid decomposition tree.

Define $$$T_X$$$ subtree of given tree that contains $$$X$$$ and consists of such vertixes $$$Y$$$ that $$$Level_X$$$ is the minimum level on path $$$XY$$$ ($$$X$$$ will be the root of such tree). From the previous fact we know that trees of vertixes of the same level don't intersect and vertex with level = $$$l$$$ is in $$$O(l)$$$ trees.

From the construction of Centroid Decomposition we know that there are at most $$$O(logN)$$$ levels.

Let's create array $$$dist[LG][N]$$$ where $$$dist[j][v]$$$ is the distance from $$$v$$$ to such $$$u$$$ that $$$Level_u = j$$$ and $$$v \in T_u$$$.

How to answer the query now? Let's check all the possibilities for the vertex with the minimum level. It should be on the path from $$$V$$$ to the root of the centroid decomposition tree. If we fix it and it's level is $$$j$$$ then we update answer with $$$dist[j][L] + dist[j][V]$$$.

What is the problem we have now? Let's look at the numbers $$$dist[j][L], dist[j][L + 1], ..., dist[j][x], ..., dist[j][R]$$$. We should update our answer using only some of them — $$$x$$$ must be in the same level $$$j$$$ tree as $$$V$$$.

Let's replace that table with the following table: $$$dist[v][u]$$$ is the distance between vertices $$$v$$$ and $$$u$$$ if $$$u \in T_v$$$ and $$$INF$$$ otherwise. This table takes $$$O(N^2)$$$ memory but only $$$O(N*logN)$$$ values are meaningful. Let's compress all rows of this table. Then we have $$$O(N)$$$ arrays and we can build a segment tree on each of them.

We can don't care about moving L and R in questions to the segment trees as I did in This submission. Hope this comment will help you.