Solução Informática - Nivel Avançado - Semana 24

Escrito por Leonardo Paes

Conhecimento prévio necessário:

• Map
• Congruências
• Soma de Prefixos

A ideia principal para resolvermos esse problema é que a soma de valores de um intervalo (subvetor) é a subtração de duas somas de prefixos do vetor original. Por exemplo: Dado o subvetor com índices de $l$ a $r$ a sua soma é $pref[r] - pref[l-1]$, onde $pref[]$ é o vetor das somas de prefixos.

Ao fixarmos o $r$, o final de um certo subvetor, basicamente queremos saber a quantidade de $l$ tal que $l \leq r$ e $pref[r] - pref[l-1] \equiv 0 \;(mod \;n)$, e isso é o mesmo que: $pref[r] \equiv pref[l-1] \;(mod \;n)$.

Para encontrarmos essa quantidade de $l$ para cada $r$, basta utilizarmos um $map$ de frequências, que diz a quantidade de prefixos anteriores a $r$ com soma congruente a um certo valor módulo $n$.

Confira o código abaixo para melhor entendimento: