Encontrar o número de elementos menores para cada elemento em uma matriz de forma eficiente

Estou preso neste problema:

Dada uma matriz dos primeiros números naturais permutados aleatoriamente, uma matriz é construída, de modo que é o número de elementos de a que são menores que . $A$$n$$B$$B(k)$$A(1)$$A(k-1)$$A(k)$

i) Dado você pode encontrar em tempo? ii) Dado você pode encontrar em tempo?$A$$B$$O(n)$
$B$$A$$O(n)$

Aqui, . Para um exemplo concreto: $B(1) = 0$

$$\begin{vmatrix} A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\ B & 0 & 0 & 0 & 0 & 3 & 1 & 6 & 4 & 4 \\ \end{vmatrix}$$

Alguém pode me ajudar? Obrigado.

$B$$A$

$k=1,\dots,n$$B(k)$$A(i)$$A(k)$$i=1,\dots,k$$A(i)<A(k)$

$A(1)$$n-1$$A(2)$$n-2$$\frac{(n-1)(n-2)}{2}$$B(n)$$B(n)=A(n)-1$ $n$$n-1$$B(n-1)$$A(1)$$A(n-2)$$A(n)$

$k=1, \dots,\frac{n}{2}$$k=\frac{n}{2},\dots,n$$B(k)$$A(n)-1$$1$$A(i)$$i=k+1,\dots,n$$A(k)$

Isso levaria etapas, que ainda é . Observe também que, ao construir partir de , se então .$2\times\frac{(\frac{n}{2}-1) (\frac{n}{2}-2)}{2}=\frac{(n-2)(n-4)}{4}$$O(n^2)$$A$$B$$B(n)=A(n)-1$$A(n)=B(n)+1$

Mas agora para mais requinte. Se for permitido um espaço adicional ou uma classificação no local, podemos classificar os números à medida que os comparamos. Por exemplo:

$$\begin{vmatrix} A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\ S & 9 & 8 & 7 & 4 & 3 & 2 & 1 & 6 & 5 \\ B & 0 & 0 & 0 & 0 & 3 & 1 & 6 & & \\ \end{vmatrix}$$

Em vez de verificar todas elas (ou verificá-las em ordem), poderíamos usar a pesquisa binária para determinar cada . No entanto, a classificação ainda leva tempo .$B(k)$$O(n\log n)$

$B(k)$$A$ $n$

$$\begin{vmatrix} A & & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & & B \\ 8 & & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \color{red}{0} & 1 & & 0\\ 4 & & 0 & 0 & 0 & \color{red}{0} & 1 & 1 & 1 & 1 & 2 & & 0\\ 3 & & 0 & 0 & \color{red}{0} & 1 & 2 & 2 & 2 & 2 & 3 & & 0\\ 1 & & \color{red}{0} & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 4 & & 0\\ 7 & & 0 & 1 & 1 & 2 & 3 & 3 & \color{red}{3} & 4 & 5 & & 3\\ 2 & & 0 & \color{red}{1} & 2 & 3 & 4 & 4 & 4 & 5 & 6 & & 1\\ 9 & & 0 & 1 & 2 & 3 & 4 & 4 & 4 & 5 & \color{red}{6} & & 6\\ 6 & & 0 & 1 & 2 & 3 & 4 & \color{red}{4} & 5 & 6 & 7 & & 4\\ 5 & & 0 & 1 & 2 & 3 & \color{red}{4} & 5 & 6 & 7 & 8 & & 4\\ \end{vmatrix}$$

$8$$\frac{(n)(n+2)}{2}$

I e II são solucionáveis ​​usando #next_gength_element que expliquei aqui . mas é um pouco mais difícil do que apenas o problema, mas antes da solução, você precisa aprender o próximo elemento:

1. $A$$S_i$$i$$i$$A$$S_i$$i$$B[i]=\sum_{j=0}^x (S_i[j]+1)$$x$$S_i$$\Theta(n)$$\Theta(n)$$\Theta(n)$

$O(1)$$o(n)$