Este problema relata uma história real, a história de Kushim que pode ser encontrada em um vídeo do Matt Parker (https://www.youtube.com/watch?v=MZVs6wF7nC4).
É necessário uma estrutura de dados que possa fazer soma em intervalo e sobrescrever o valor em uma posição de forma rápida. Pelo menos duas podem ser usadas para este papel: Árvore de segmentos e árvore de Fenwick (que é usada na solução do juiz), que permitem que estas duas operações sejam feitas em $$$\mathcal{O}(\lg n)$$$. Em cada posição da estrutura de dados, inicialmente coloca-se cada dígito da fita, $$$\mathcal{O}(n \lg n)$$$.
Com as propriedades enunciadas, para verificar uma soma ou multiplicação, basta somar os dígitos de cada operando do intervalo $$$\pmod 9$$$, em seguida realizar a operação com os dois resultados, e por fim, comparar com o dígito de verificação dado. Para colocar um dígito na posição em uma árvore de Fenwick, é necessário manter o vetor original e computar um $$$\Delta d$$$ para mudar o valor naquela posição.
A solução então possui complexidade $$$O(n \lg n + q \lg n)$$$.