Comentário por Henrique Vianna
Conhecimento prévio necessário:
Nesse exercicio, dada uma lista de $$N$$ dominós, deve-se computar para cada um quantos outros dominós ele derruba, seja diretamente ou indiretamente. Um dominó $$i$$ atinge um outro dominó $$j$$ de forma direta se, e somente se, $$i > j$$ e $$x[i] + h[i] \geq x[j]$$.
Intuitivamente, faz sentido calcularmos as respostas para cada um dos dominós em ordem decrescente (de $$N$$ a $$1$$), uma vez que um dado dominó só pode afetar aqueles que estão para a sua direita. Para nos auxiliar nessa tarefa, faremos uso de uma stack chamada de ativos, que guardará os índices dos dominós ainda não derrubados. Ademais, seja $$f[i]$$ o número de dominós que o dominó $$i$$ derruba. Então, tendo já calculado $$f[j]$$ para $$j > i$$ e mantendo essa stack, basta fazermos:
$$f[i] = 1 + \sum_{j \in ativos}f[j]$$, se $$x[i] + h[i] \geq x[j]$$.
Perceba que se o dominó atual derrubar um dado dominó $$j$$ de ativos, então deve-se remover $$j$$ da stack. Ao acabarmos de processarmos o dominó $$i$$, devemos inseri-lo em ativos e avançar para o dominó $$i – 1$$. Perceba que, uma vez que inserimos e retiramos um dado dominó da nossa stack uma única vez, a complexidade de nosso algoritmo é $$\mathcal{O}(N)$$. Ao final, basta imprimirmos $$f[i]$$ para $$1 \leq i \leq N$$.